Login
Talks & Seminars
Title: The Strahler Analysis of Binary Trees in Computer Science and in Other Sciences
Prof. Xavier Viennot, LaBRI, France
Date & Time: February 14, 2013 15:00
Venue: Conference Room, 01st Floor, C Block, Department of Computer Science and Engineering, Kanwal Rekhi Building
Abstract:
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 hydro-geology (Horton, Strahler) for the morphologic study of river networks, and also in molecular biology in the study of RNA secondary structures (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.
Speaker Profile:
Details about speaker are available at http://www.labri.fr/perso/viennot/.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback