Applications of Generating Functions
Organizer and Chair:
Alois Panholzer (Technische UniversitÃ¤t Wien)
[
PDF]
 MARIELOUISE BRUNER, Vienna University of Technology, Austria
Parking in trees [PDF] [SLIDES]

We generalize the intensively studied concept of parking functions to trees. This leads to the following setting: Given a rooted unordered tree with $n$ nodes, $m$ drivers try to park at their specific preferred parking spot. If this node is already occupied, the driver moves on to the next node lying closer to the root. How many assignments of preferred parking spots are there that allow all drivers to park successfully? We answer this question both with exact and asymptotic enumeration results and further generalize this concept to mappings.
This is joint work with Alois Panholzer.
 BERNHARD GITTENBERGER, TU Wien
Associative and commutative tree representations for Boolean functions [PDF]

Since twenty years several authors have studied probability distributions on the set of Boolean functions in $n$ variables induced by distributions on the set of formulas built upon the connectors $And$ and $Or$ and the literals $\{x_{1}, \bar{x}_{1}, \dots, x_{n}, \bar{x}_{n}\}$. These formulas rely on plane binary labelled trees. We extend these results, in particular the relation between probability and complexity of Boolean functions, to other models: nonbinary or nonplane labelled trees. This includes the natural tree class where associativity and commutativity of $And$, and $Or$ are realised.
This is joint work with Antoine Genitrini, Veronika Kraus and C\'ecile Mailler.
 HELMUT PRODINGER, University of Stellenbosch
Generating functions in the analysis of $m$versions of approximate counting, binary search trees and other structures [PDF] [SLIDES]

It was recently suggested to use $m$ counters instead of the usual one in approximate counting. The analysis of this $m$version leads to many interesting developments. It is also natural to introduce $m$versions for other combinatorial structures: binary search trees, digital search trees, plane oriented recursive trees, and words. It will be described how classical results can be translated via substitutions in suitable generating functions.
 ALFREDO VIOLA, Universidad de la RepÃºblica, Montevideo, URUGUAY
Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields [PDF] [SLIDES]

We present counting methods for some special classes of
multivariate polynomials over a finite field, namely the reducible ones, the
$s$powerful ones (divisible by the $s$th power of a nonconstant
polynomial), and the relatively irreducible ones (irreducible but reducible
over an extension field). One approach employs generating functions,
another one a combinatorial method. They yield exact formulas and approximations with relative
errors that essentially decrease exponentially in the input size. This is joint work with Joachim von zur Gathen and Konstantin Ziegler.
 MARK DANIEL WARD, Purdue University
Recent Directions in Tries, Pattern Matching, Suffix Trees, and Subword Complexity [PDF]

We survey recent developments in pattern matching that directly apply to the analysis of retrieval trees (tries) and to the subword complexity of strings. In particular, we discuss the methodology for precise asymptotic analysis of the variance of subword complexity and the profile of suffix trees.