Self-avoiding walks and multiple context-free languages

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 ⁿ 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.