Automata on S-adic words

Abstract: O. Carton and W. Thomas gave, in 2002, an algorithm for deciding whether a given automaton $A$ over infinite words accept a given morphic word $u$. Together with V. Berthé and M. Vahanwala, we study the same automaton acceptance problem in the more general setting of $S$-adic words. Among other results, we show how to compute, given a set $S$ of substitutions and an automaton $A$, an automaton $B$ that accepts a sequence $s$ over $S$ if and only if $s$ directs a word accepted by $A$. Thus we are able to completely answer questions of the form "Which Sturmian words $u$ are accepted by a given automaton $A$?" In particular, we show that whether $A$ accepts $u$ is completely determined by the first $N$ (that depends only on $A$) partial quotients of the slope of $u$. Our main tools are monoids and a new (?) structure theorem for $S$-adic expansions.

dynamical systemsnumber theory

Audience: researchers in the topic

( paper )

---

One World Numeration seminar

Series comments: Description: Online seminar on numeration systems and related topics

For questions or subscribing to the mailing list, contact the organisers at numeration@irif.fr

---