Walking On A Line: finding S-adic walks in an ω-automaton

-- Pierre Béaur (LISN, Galac)

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.

Category: seminars
Tags: Team seminar combinatorics