Walking On A Line: finding S-adic walks in an ω-automaton
Time: 14:00 -- Location: LRI, 445
summary: At the heart of symbolic dynamics lies the study of languages, infinite words and the
dynamical structures associated. We focus on two classical methods to generate such structures.
The first one relies on substitutions, which are morphisms on words, by iterating one on an
initial letter, and considering the limit word. This substitutive approach was generalized by
allowing the use of multiple substitutions, thus leading to the notion of S-adic representations.
The second method to generate symbolic structures is to consider the infinite walks on a labeled
graph (or ω-automaton).
In this presentation, I consider decidability questions at the crossing between these two points
of view. Given an ω-automaton A, and a substitution σ, does A accept the infinite substitutive words
generated by σ? The main result of this presentation is that, using elementary notions of formal
languages, we can build a new tool to decide such questions. In the S-adic framework, this tool also
solves similar questions: given an ω-automaton A, does A accept a Sturmian word? an Arnoux-Rauzy word?
We also use this tool to derive results on the structure of S-adic representations allowed in an
ω-automaton, on the structure of ω-automata accepting substitutive words, and on the combinatorics
of Sturmian words.