Vortrag im Rahmen des Doctoral Seminar in Mathematics von Herrn Andrei Asinowski
Veranstaltungsort
N.2.01
Veranstalter
Institut für Mathematik
Beschreibung
Titel:
Enumeration of lattice paths with forbidden patterns
Kurzfassung:
A lattice path is a word (a_1, …, a_n) over an alphabet S, a pre-chosen set of integer numbers. It is visualized as a polygonal line which starts at the origin and consists of the vectors (1, a_i), i=1..n, appended to each other.
In 2002, Banderier and Flajolet found general expressions for generating functions that enumerate several classes of lattice paths („walks“, „bridges“, „meanders“, and „excursions“).
We extend and refine the study of Banderier and Flajolet by considering lattice paths that avoid a „pattern“ – a fixed word p. We obtain expressions that generalize those from the work by Banderier and Flajolet.
Our main tool is a combination of finite automata machinery with a novel multidimensional extension of the so-called kernel method. Via the link between lattice paths and pushdown automata, this method can be generally applied to enumeration of formal languages generated by context-free grammars.
(Joint work with A. Bacher, C. Banderier and B. Gittenberger.)
Vortragende(r)
Andrei Asinowski
Kontakt
Senka Haznadar (senka [dot] haznadar [at] aau [dot] at)
Ähnliche Veranstaltungen
