Re: Combinatorics of algebraic expressions

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

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