TY - JOUR
T1 - Self-avoiding walks and multiple context-free languages
AU - Lehner, Florian
AU - Lindorfer, Christian
PY - 2023
Y1 - 2023
N2 - Let G be a quasi-transitive, locally finite, connected graph rooted at a vertex o, and let c
n (o) be the number of self-avoiding walks of length n on G starting at o. We show that if G has only thin ends, then the generating function F
SAW,o (z) =
∑n⩾1
cn(o)z
n is an algebraic function. In particular, the connective constant of such a graph is an algebraic number. If G is deterministically edge-labelled, that is, every (directed) edge carries a label such that no two edges starting at the same vertex have the same label, then the set of all words which can be read along the edges of self-avoiding walks starting at o forms a language denoted by L
SAW,o . Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that L
SAW,o is a k-multiple context-free language if and only if the size of all ends of G is at most 2k. Applied to Cayley graphs of finitely generated groups this says that L
SAW,o is multiple context-free if and only if the group is virtually free.
AB - Let G be a quasi-transitive, locally finite, connected graph rooted at a vertex o, and let c
n (o) be the number of self-avoiding walks of length n on G starting at o. We show that if G has only thin ends, then the generating function F
SAW,o (z) =
∑n⩾1
cn(o)z
n is an algebraic function. In particular, the connective constant of such a graph is an algebraic number. If G is deterministically edge-labelled, that is, every (directed) edge carries a label such that no two edges starting at the same vertex have the same label, then the set of all words which can be read along the edges of self-avoiding walks starting at o forms a language denoted by L
SAW,o . Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that L
SAW,o is a k-multiple context-free language if and only if the size of all ends of G is at most 2k. Applied to Cayley graphs of finitely generated groups this says that L
SAW,o is multiple context-free if and only if the group is virtually free.
KW - Cayley graph
KW - formal language
KW - multiple context free language
KW - Self avoiding walk
KW - virtually free group
UR - http://www.scopus.com/inward/record.url?scp=85170053675&partnerID=8YFLogxK
U2 - https://doi.org/10.5070/C63160431
DO - https://doi.org/10.5070/C63160431
M3 - Article
SN - 2766-1334
VL - 3
JO - Combinatorial Theory
JF - Combinatorial Theory
IS - 1
M1 - #18
ER -