Wed, 20 Apr 1994 17:24:15 GMT

Related articles |
---|

Combinatorics of algebraic expressions szabo@netcom.com (1994-04-16) |

Re: Combinatorics of algebraic expressions Philippe.Flajolet@inria.fr (1994-04-20) |

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",

title = "Advanced Combinatorics",

publisher = "Reidel",

year = "1974",

address = "Dordrecht"

*}*

@book{Knuth68,

author = "Donald E. Knuth",

year = 1968,

title = "The Art of Computer Programming",

volume = "1: Fundamental Algorithms",

publisher = "Addison-Wesley",

note = "Second edition, 1973"

}

@Book{HaPa73,

author = "Frank Harary and Edgar M. Palmer",

title = "Graphical Enumeration",

publisher = "Academic Press",

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.