The language of self-avoiding walks (Christian Lindorfer, TU Graz)

27.09.2022 10:30

Let X be the Cayley graph of a finitely generated group with respect to some finite, symmetric generating set, where each directed edge is labelled with its generator. The language of self-avoiding walks consists of all words which can be read along self-avoiding walks on X.
In this talk we discuss a recent characterisation of the language of self-avoiding walks on virtually free groups. This language is k-multiple context-free if and only if the size of all ends of X is at most 2k. More generally, this result also holds for deterministically labelled quasi-transitive graphs. Moreover, our approach shows that the connective constant of any thin-ended quasi-transitive graph is an algebraic number.

Lieu

Bâtiment: Conseil Général 7-9

Room 1-05, Tuesday 27.09.2022, Séminaire "Groupes et géométrie"

entrée libre