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.
Speakers 1
Past sessions
Resources 1
Discussion 0 Open full thread →
Similar Events
Claim this event
If you are the organizer of this event on researchseminars.org, you can request to claim it on Androma. This will let you manage the event, add prerequisites, and link it to your Androma profile.
Claim submitted. An admin will review your request.