The Language of Self-Avoiding Walks

Christian Lindorfer*, Wolfgang Woess

*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung


Let X = (VX, EX) be an infinite, locally finite, connected graph without loops or multiple edges. We consider the edges to be oriented, and EX is equipped with an involution which inverts the orientation. Each oriented edge is labelled by an element of a finite alphabet Σ. The labelling is assumed to be deterministic: edges with the same initial (resp. terminal) vertex have distinct labels. Furthermore, it is assumed that the group of label-preserving automorphisms of X acts quasi-transitively. For any vertex o of X, consider the language of all words over Σ which can be read along self-avoiding walks starting at o. We characterize under which conditions on the graph structure this language is regular or context-free. This is the case if and only if the graph has more than one end, and the size of all ends is 1, or at most 2, respectively.

Seiten (von - bis)691-720
Frühes Online-Datum2020
PublikationsstatusVeröffentlicht - Nov. 2020

ASJC Scopus subject areas

  • Computational Mathematics
  • Diskrete Mathematik und Kombinatorik

Fields of Expertise

  • Information, Communication & Computing


Untersuchen Sie die Forschungsthemen von „The Language of Self-Avoiding Walks“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren