Projects per year
Abstract
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 labelpreserving automorphisms of X acts quasitransitively. For any vertex o of X, consider the language of all words over Σ which can be read along selfavoiding walks starting at o. We characterize under which conditions on the graph structure this language is regular or contextfree. 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.
Original language  English 

Pages (fromto)  691720 
Number of pages  30 
Journal  Combinatorica 
Volume  40 
Issue number  5 
Early online date  2020 
DOIs  
Publication status  Published  Nov 2020 
ASJC Scopus subject areas
 Computational Mathematics
 Discrete Mathematics and Combinatorics
Fields of Expertise
 Information, Communication & Computing
Fingerprint
Dive into the research topics of 'The Language of SelfAvoiding Walks'. Together they form a unique fingerprint.Projects
 1 Active

Doctoral Program: Discrete Mathematics
Ebner, O., Lehner, F., Greinecker, F., Burkard, R., Wallner, J., Elsholtz, C., Woess, W., Raseta, M., Bazarova, A., Krenn, D., Lehner, F., Kang, M., Tichy, R., SavaHuss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Project: Research project