LIPN: CALIN


Cyril Banderier's list of talks


           Cyril Banderier           Cyril Banderier
Laboratoire d'Informatique de Paris-Nord
UMR CNRS 7030
Institut Galilée - Université Paris-Nord
99, avenue Jean-Baptiste Clément
93430 Villetaneuse
France

Office: A106
Phone: +33 1 49 40 40 69
Fax:     +33 1 48 26 07 12
E-mail: Cyril.Banderier at lipn.univ-paris13.fr


"The Airy function in combinatorics and analysis of algorithms"

by Cyril Banderier, Univ. Paris 13, France.

The Airy function is a special function from physics, which solves many problems in optics, quantum mechanics, and it was a nice surprise that it plays also a role in combinatorics.

Analytic combinatorics is a field, mainly developped by Philippe Flajolet, which is using generating functions to analyse combinatorial structures: their recursive definition is transformed in recurrence, which is transformed into a power series, on which complex analysis gives asymptotic results.

As well illustrated by Don Knuth, this allows to describe the complexity of many algorithms in computer science.

I will illustrate how analytic combinatorics allows to prove that the Airy functions appears in several combinatorial problems (random walks, hashing, graphs, random generation, attribute grammars...), and why it allows to improve related algorithms.


"Random walks and analytic combinatorics"

Cyril Banderier, Univ. Paris 13, France

Analytic combinatorics is a field, mainly developed by Philippe Flajolet, which is using generating functions to analyze combinatorial structures: their recursive definition is transformed in recurrence, which is transformed into a power series, on which complex analysis gives asymptotic results. I will illustrate how analytic combinatorics (and the so-called "kernel method") allows to enumerate a huge variety of constrained random walks (bridges, excursions, meanders), to give their typical "shape" (asymptotics and limit laws), including for non trivial parameters like the height and the area. This includes combinatorial models like lattice paths (generalized Dyck path), some families of trees, some context-free grammars.

"Context-free grammars and analytic combinatorics"

Cyril Banderier, Univ. Paris 13, France

The theory of formal languages and their counterparts in linguistics (as considered by the linguist Noam Chomsky and the mathematician Marcel-Paul Schützenberger) has many application in computer science, and also in combinatorics. Indeed, the so-called "context free grammars" are a powerful tool to enumerate and generate structures like words, trees, random walks, polyominoes. Analytic combinatorics is a field, mainly developed by Philippe Flajolet, which is using generating functions to analyze combinatorial structures: their recursive definition is transformed in recurrence, which is transformed into a power series, on which complex analysis gives asymptotic results. I will illustrate how analytic combinatorics allows to get results on context-free grammars (i.e. on algebraic systems of equations). I will give explicit formulae, and questions with a taste of number theory. Context-free grammars can be considered as the non-commutative version of systems of polynomial equations. (The specific case of linear system equation corresponds to automata theory, also known as "Markov chains" in the probabilist world). In one sense, we get the "polynomial" version of the Perron-Frobenius theorem. Let f_n be the number of words of length n generated by a context-free grammar. A recent result of Banderier & Drmota shows that f_n~C. A^n n^e where e (which is called the "critical exponent") belongs to a subset of dyadic numbers. A contrario, it is nice that complex analysis thus gives a way to prove that some type of random walks or planar maps cannot be generated by such grammars. We will also consider multivariate versions, and corresponding limit laws.