Automata on $S$-adic words
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911016518942720 |
|---|---|
| author | Berthé, Valérie Karimov, Toghrul Vahanwala, Mihir |
| author_facet | Berthé, Valérie Karimov, Toghrul Vahanwala, Mihir |
| contents | A fundamental question in logic and verification is the following: for which unary predicates $P_1, \ldots, P_k$ is the monadic second-order theory of $\langle \mathbb{N}; <, P_1, \ldots, P_k \rangle$ decidable? Equivalently, for which infinite words $α$ can we decide whether a given Büchi automaton $A$ accepts $α$? Carton and Thomas showed decidability in case $α$ is a fixed point of a letter-to-word substitution $σ$, i.e., $σ(α) = α$. However, abundantly more words, e.g., Sturmian words, are characterised by a broader notion of self-similarity that uses a set $S$ of substitutions. A word $α$ is said to be directed by a sequence $s = (σ_n)_{n \in \mathbb{N}}$ over $S$ if there is a sequence of words $(α_n)_{n \in \mathbb{N}}$ such that $α_0 = α$ and $α_n = σ_n(α_{n+1})$ for all $n$; such $α$ is called $S$-adic. We study the automaton acceptance problem for such words and prove, among others, the following. Given finite $S$ and an automaton $A$, we can compute an automaton $B$ that accepts $s \in S^ω$ if and only if $s$ directs a word $α$ accepted by $A$. Thus we can algorithmically answer questions of the form "Which $S$-adic words are accepted by a given automaton $A$?" |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17460 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Automata on $S$-adic words Berthé, Valérie Karimov, Toghrul Vahanwala, Mihir Formal Languages and Automata Theory Logic in Computer Science A fundamental question in logic and verification is the following: for which unary predicates $P_1, \ldots, P_k$ is the monadic second-order theory of $\langle \mathbb{N}; <, P_1, \ldots, P_k \rangle$ decidable? Equivalently, for which infinite words $α$ can we decide whether a given Büchi automaton $A$ accepts $α$? Carton and Thomas showed decidability in case $α$ is a fixed point of a letter-to-word substitution $σ$, i.e., $σ(α) = α$. However, abundantly more words, e.g., Sturmian words, are characterised by a broader notion of self-similarity that uses a set $S$ of substitutions. A word $α$ is said to be directed by a sequence $s = (σ_n)_{n \in \mathbb{N}}$ over $S$ if there is a sequence of words $(α_n)_{n \in \mathbb{N}}$ such that $α_0 = α$ and $α_n = σ_n(α_{n+1})$ for all $n$; such $α$ is called $S$-adic. We study the automaton acceptance problem for such words and prove, among others, the following. Given finite $S$ and an automaton $A$, we can compute an automaton $B$ that accepts $s \in S^ω$ if and only if $s$ directs a word $α$ accepted by $A$. Thus we can algorithmically answer questions of the form "Which $S$-adic words are accepted by a given automaton $A$?" |
| title | Automata on $S$-adic words |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2506.17460 |