The language of self-avoiding walks (Q2658381)

The objective of this paper is to connect the study of self-avoiding walks with the theory of formal languages. For an infinite, locally finite, connected graph without loops or multiple edges, the authors label the oriented edges by elements of a finite alphabet deterministically, i.e., edges with the same initial or terminal vertex have distinct labels. They also consider that the label-preserving automorphism group acts quasi-transitively on the graph, i.e., that there are finitely many orbits on the set of vertices.\par In this context, the language of self-avoiding walks for some start vertex \(o\) is the formal language that consists of the words read along sequences of edge-connected vertices starting at \(o\) for which no vertex is visited twice. The main results of the paper characterize when this language is regular or context-free. Namely, the authors show that for any vertex \(o\), this language is regular exactly when the graph has more than one end, and the size of all ends is \(1\). Furthermore, they show that this language is context-free exactly when the graph has more than one end and all ends are of size at most \(2\).\par Ends of a connected graph, a notion introduced by \textit{R. Halin} [Math. Ann. 157, 125--137 (1964; Zbl 0125.11701)] are equivalence classes of infinite paths that are included, but for finitely many elements, in the same component when finitely many vertices are removed.\par The authors use cut-vertex tree decompositions to show that the language is regular and the 3-block tree decompositions of \textit{C. Droms} et al. [Electron. J. Comb. 2, 271--280 (1995; Zbl 0829.05041)] to show that it is context-free. As their proof is constructive, they finally discuss how the obtained grammar can be used to calculate the generating function of self-avoiding walks and determine related invariants.