# Re: Combinatorics of algebraic expressions

## Philippe.Flajolet@inria.fr (Philippe Flajolet)Wed, 20 Apr 1994 17:24:15 GMT

From comp.compilers

Related articles
Combinatorics of algebraic expressions szabo@netcom.com (1994-04-16)
Re: Combinatorics of algebraic expressions Philippe.Flajolet@inria.fr (1994-04-20)
| List of all articles for this month |

 Newsgroups: sci.math,comp.theory,comp.compilers From: Philippe.Flajolet@inria.fr (Philippe Flajolet) Keywords: theory, bibliography Organization: INRIA-Rocquencourt, France References: 94-04-111 Date: Wed, 20 Apr 1994 17:24:15 GMT

Counting expressions in various types of algebras reduces to counting
trees with possible constraints. This is a well known combinatorics
problem. One of the best references for early work is Comtet's book.
There is also a good introductory section on tree enumerations in Knuth,
vol 1.

For instance:
-- it is well known that the number of terms with a noncommutative
nonassociative operation and 1 variable symbol is the
Catalan number 1/n{2n choose n} (n the number of variables
=> n-1 operations). The best proof is by generating functions.
See Graham-Knuth-Patashnik for an elementary introduction.
If there are m different types of variables, just multiply
the Catalan number by m^n.
-- for a commutative-non associative operation, the asymptotic counting
was done by Otter (see Knuth, Comtet): the problem is equivalent to
counting "non-plane" trees.
-- for an associative noncommutative operation, you're just counting
words over an m-ary alphabet (m the number of variables).
In all these problems, the answer tends to be asymptotically of the form
C * A^n n^{-3/2}
where the constants C and A are explicitly computable given the type
of operators considered. (See Harary & Palmer, Meir and Moon).

A lot is also known about probabilistic properties of these term
trees: height tends to be O(sqrt(n)) for a random tree of size n, for
instance. Patterns occur in trees more or less with the same geometric
distribution as in strings, the common subexpression problem can be
analysed as can be various forms of term rewritings, etc... (See also
ViFl90 for a partial survey of the methods.)

I include a collection of references on these problems.

Philippe Flajolet

@Book{Comtet74,
author = "Louis Comtet",
publisher = "Reidel",
year = "1974",
}

@book{Knuth68,
author = "Donald E. Knuth",
year = 1968,
title = "The Art of Computer Programming",
volume = "1: Fundamental Algorithms",
note = "Second edition, 1973"
}

@Book{HaPa73,
author = "Frank Harary and Edgar M. Palmer",
title = "Graphical Enumeration",
year = "1973"
}

@article{MeMo78,
author = "A. Meir and J. W. Moon",
title = "On the altitude of nodes in random trees",
journal = CJM,
volume = 30,
year = 1978,
pages = "997--1015",
keywords = "random trees"
}
@string{CJM = "Canadian Journal of Mathematics"}

@article{StFl83,
author = "J-M. Steyaert and P. Flajolet",
year = "1983",
journal = IC,
title = "Patterns and Pattern-Matching in Trees: an Analysis",
volume = "58",
number = "1--3",
month = jul,
pages = "19--58"
}
@string{IC = "Information and Control"}

@Article{ChKaSo89,
author = "Christine Choppy and St{\'e}phane Kaplan and
Mich{\`e}le Soria",
title = "Complexity analysis of Term Rewriting Systems",
journal = TCS,
year = 1989,
volume = "67",
pages = "261--282"
}
@string{TCS = "Theoretical Computer Science"}

@InProceedings{AlCaFaToZi91,
author = "Luc Albert and Rafael Casas and Fran{\c c}ois Fages
and A. Torrecillas and Paul Zimmermann",
title = "Average Case Analysis of Unification Algorithms",
booktitle = "Proceedings of STACS'91",
series = LNCS,
year = "1991",
pages = "196--213",
editor = "C. Choffrut and M. Jantzen",
keywords = "unification, tree algorithm"
}

@InProceedings{FlSiSt90,
author = "Philippe Flajolet and Paolo Sipala and Jean--Marc Steyaert",
title = "Analytic Variations on the Common Subexpression Problem",
series = LNCS,
booktitle = "Automata, Languages, and Programming",
year = "1990",
volume = 443,
editor = "M. S. Paterson",
pages = "220--234",
note = "Proceedings of the 17th ICALP Conference, Warwick, July 1990"
}

@Article{FlSaZi91,
author = "P. Flajolet and B. Salvy and P. Zimmermann",
title = "Automatic Average--case Analysis of Algorithms",
journal = TCS,
volume = "79",
number = "1",
year = 1991,
month = feb,
pages = "37--109"
}

@article{FlOd82,
author = "P. Flajolet and A. Odlyzko",
year = "1982",
journal = JCSS,
pages = "171--213",
title = "The average Height of Binary trees and Other Simple Trees",
volume = "25"
}
@string{JCSS = "Journal of Computer and System Sciences"}

@Article{FlGaOdRi93,
author = "Philippe Flajolet and Zhicheng Gao and Andrew Odlyzko
and Bruce Richmond",
title = "The Distribution of Heights of Binary Trees and Other
Simple Trees",
year = "1993",
journal = "Combinatorics, Probability and Computing",
volume = 2,
pages = "145--156",
keywords = "height of trees, limit distribution, iteration"
}

@incollection{ViFl90,
author = "Jeffrey Scott Vitter and Philippe Flajolet",
year = "1990",
title = "Analysis of Algorithms and Data Structures",
booktitle = "Handbook of Theoretical Computer Science",
volume = "A: Algorithms and Complexity",
chapter = "9",
editor = "J. van Leeuwen",
publisher = "North Holland",
pages = "431--524"
}
--

Post a followup to this message