Androma
Talk Analysis Number Theory Virtual

Automata on S-adic words


12:00 – 13:00 (Paris)
Virtual Event
Sourced from
researchseminars.org  
Sign in to RSVP
Get stream access Add to calendar

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

TK
Toghrul Karimov

Past sessions

Jun 16
Restricted polynomial roots, reciprocal power series, and finite capture for collinear affine IFS
View

Resources 1

Discussion 0 Open full thread →

No comments yet. to start the discussion. No comments yet. Be the first to share your thoughts!

Similar Events

Event data sourced from researchseminars.org. Androma is not affiliated with researchseminars.org.

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.

Tue, Jun 30 · 12:00 (Paris)
Sign in to RSVP