Automatic winning shifts
| Autor: | Peltomäki, Jarkko, Salo, Ville |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Information and Computation, Vol. 285.B, 104883:1-21 (2022) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.ic.2022.104883 |
| Popis: | To each one-dimensional subshift $X$, we may associate a winning shift $W(X)$ which arises from a combinatorial game played on the language of $X$. Previously it has been studied what properties of $X$ does $W(X)$ inherit. For example, $X$ and $W(X)$ have the same factor complexity and if $X$ is a sofic subshift, then $W(X)$ is also sofic. In this paper, we develop a notion of automaticity for $W(X)$, that is, we propose what it means that a vector representation of $W(X)$ is accepted by a finite automaton. Let $S$ be an abstract numeration system such that addition with respect to $S$ is a rational relation. Let $X$ be a subshift generated by an $S$-automatic word. We prove that as long as there is a bound on the number of nonzero symbols in configurations of $W(X)$ (which follows from $X$ having sublinear factor complexity), then $W(X)$ is accepted by a finite automaton, which can be effectively constructed from the description of $X$. We provide an explicit automaton when $X$ is generated by certain automatic words such as the Thue-Morse word. Comment: 28 pages, 5 figures, 1 table |
| Databáze: | arXiv |
| Externí odkaz: |
|