Cyril Banderier's list of talks

 
Cyril Banderier
Laboratoire d'Informatique de ParisNord
UMR CNRS 7030
Institut Galilée  Université ParisNord
99, avenue JeanBaptiste Clément
93430 Villetaneuse
France
Office: A106
Phone: +33 1 49 40 40 69
Fax: +33 1 48 26 07 12
Email: Cyril.Banderier at lipn.univparis13.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 socalled "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 contextfree grammars.
"Contextfree 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
MarcelPaul Schützenberger) has many application in computer science,
and also in combinatorics.
Indeed, the socalled "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 contextfree grammars (i.e. on algebraic systems of equations).
I will give explicit formulae, and questions with a taste of number theory.
Contextfree grammars can be considered as the noncommutative
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 PerronFrobenius theorem.
Let f_n be the number of words of length n generated by a contextfree 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.