Projects per year
Abstract
This is an introductory review of recent work on selfavoiding walks on thinended quasitransitive graphs. The goal is not to give precise proofs, but instead show the main ideas by giving simple examples.
Our main interest lies in two different kinds of formal languages induced by the set of all selfavoiding walks on the graph starting at a given origin. The language of selfavoiding walks on a deterministically edgelabelled graph consists of all words obtained by reading along selfavoiding walks. We discuss that this language is regular or contextfree, if and only if the given graph has ends of size at most 1 or 2, respectively.
Using treedecomposition, thin ended graphs can be decomposed into finite parts. Configurations are appearances of selfavoiding walks on single parts, and compatible configurations on the composition tree correspond to selfavoiding walks on the original graph. By encoding compatible configurations as words we obtain the language of configurations. This language is contextfree and thus the generating function of selfavoiding walks is algebraic.
Our main interest lies in two different kinds of formal languages induced by the set of all selfavoiding walks on the graph starting at a given origin. The language of selfavoiding walks on a deterministically edgelabelled graph consists of all words obtained by reading along selfavoiding walks. We discuss that this language is regular or contextfree, if and only if the given graph has ends of size at most 1 or 2, respectively.
Using treedecomposition, thin ended graphs can be decomposed into finite parts. Configurations are appearances of selfavoiding walks on single parts, and compatible configurations on the composition tree correspond to selfavoiding walks on the original graph. By encoding compatible configurations as words we obtain the language of configurations. This language is contextfree and thus the generating function of selfavoiding walks is algebraic.
Original language  English 

Pages (fromto)  1126 
Number of pages  16 
Journal  Internationale Mathematische Nachrichten 
Volume  74 
Issue number  244 
Publication status  Published  Aug 2020 
ASJC Scopus subject areas
 Discrete Mathematics and Combinatorics
Fields of Expertise
 Information, Communication & Computing
Fingerprint
Dive into the research topics of 'Selfavoiding walks and their languages'. 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