Lade Veranstaltungen

Diese Veranstaltung hat bereits stattgefunden.

Vortrag im Rahmen des Doctoral Seminar in Mathematics von Herrn Andrei Asinowski

| |
Veranstaltungskategorie Vortrag

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)