|Re: math expressions optimalization email@example.com (Tomasz Kowaltowski) (2002-06-17)|
|History: Strahler or Ershov? firstname.lastname@example.org (Tomasz Kowaltowski) (2008-05-05)|
|From:||Tomasz Kowaltowski <email@example.com>|
|Date:||Mon, 05 May 2008 15:10:09 -0300|
|Posted-Date:||05 May 2008 17:15:22 EDT|
There is a well known algorithm to compute the minimal number of
registers (or stack positions) necessary to evaluate an expression
tree, based on a recursive bottom up numbering of its nodes. This kind
of numbering was introduced in 1952 by A. N. Strahler, a geoscience
professor at Columbia University, in order to classify river streams
with regard to their tributaries.
On the other hand, several texts attribute this numbering to the Russian
computer scientist A. Ershov. For instance, the "Dragon Book" uses the
term "Ershov numbers" and does not mention Strahler at all. Anybody
there knows why?
PS: Some years ago I posted a message about these numbers:
[I suspect it's because most people never heard of Strahler. I hadn't
until you wrote about him in 2002, then forgot until now. The first
edition of the Dragon Book called it Sethi-Ullman numbers, after two
guys at Bell Labs (including one of the authors) who reinvented
Return to the
Search the comp.compilers archives again.