History: Strahler or Ershov?

Tomasz Kowaltowski <tk@ic.unicamp.br>
Mon, 05 May 2008 15:10:09 -0300

          From comp.compilers

Related articles
Re: math expressions optimalization tomasz@ic.unicamp.br (Tomasz Kowaltowski) (2002-06-17)
History: Strahler or Ershov? tk@ic.unicamp.br (Tomasz Kowaltowski) (2008-05-05)
| List of all articles for this month |

From: Tomasz Kowaltowski <tk@ic.unicamp.br>
Newsgroups: comp.compilers
Date: Mon, 05 May 2008 15:10:09 -0300
Organization: IC/UNICAMP
References: 02-06-053
Keywords: registers, history
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?

-- Tomasz

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
it. -John]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.