 Main
Selfavoiding walks and multiple contextfree languages
Abstract
Let \(G\) be a quasitransitive, locally finite, connected graph rooted at a vertex \(o\), and let \(c_n(o)\) be the number of selfavoiding walks of length \(n\) on \(G\) starting at \(o\). We show that if \(G\) has only thin ends, then the generating function \(F_{\mathrm{SAW},o}(z)=\sum_{n \geq 1} c_n(o) z^n\) is an algebraic function. In particular, the connective constant of such a graph is an algebraic number.
If \(G\) is deterministically edgelabelled, 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 selfavoiding walks starting at \(o\) forms a language denoted by \(L_{\mathrm{SAW},o}\). Assume that the group of labelpreserving graph automorphisms acts quasitransitively. We show that \(L_{\mathrm{SAW},o}\) is a \(k\)multiple contextfree 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_{\mathrm{SAW},o}\) is multiple contextfree if and only if the group is virtually free.
Mathematics Subject Classifications: 20F10, 68Q45, 05C25
Keywords: Self avoiding walk, formal language, multiple context free language, Cayley graph, virtually free group
Main Content
Enter the password to open this PDF file:













