The Strahler Analysis of Binary Trees in Computer Science and in Other Sciences

Computer scientists defined the Strahler number of a binary tree in relation with  the minimum number of registers needed for the computation of an arithmetical expression. Beautiful asymptotic analysis for the average Strahler number have been done (Flajolet, Vuillemin, Raoult, Kemp), involving a periodic function coming from number theory. Surprisingly, this parameter appear in hydrogeology (Horton, Strahler) for the morphologic study of river networks, and also in molecular biology in the study of RNA secondary structure(Waterman).

Applications have been made in computer graphics (synthetic images of trees), the study of some fractal structures in experimental physics, in radiology and in the domain of visualization of informations. Underlying this asymptotic analysis, there are deep combinatorial mathematics, and some new structures have been introduced, in collaboration with D.Knuth, called Kepler towers. These objects belongs to the "heaps of pieces" theory, which gives a geometric interpretation of equivalence classes of words in the so-called "trace monoid" introduced in computer science by Mazurkiewicz as a model for concurrency access to data structures.