[:is]Málstofa í stærðfræði
Fyrirlesari: Wolfgang Woess, TU Graz
Titill: THE LANGUAGE OF SELF-AVOIDING WALKS
Staðsetning: VR-II, V-155
Tími: þriðjudagur 4. júní kl. 11.00
Ágrip:
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. (joint work with Christian Lindorfer).[:en]
Math Colloquium
Speaker: Wolfgang Woess, TU Graz
Title: THE LANGUAGE OF SELF-AVOIDING WALKS
Location: VR-II, V-155
Time: Tuesday June 4 at 11.00 am
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 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. (joint work with Christian Lindorfer). [:]