A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Automatic winning shifts
Tekijät: Peltomäki Jarkko, Salo Ville
Kustantaja: Elsevier Inc.
Julkaisuvuosi: 2022
Journal: Information and Computation
Tietokannassa oleva lehden nimi: Information and Computation
Artikkelin numero: 104883
Vuosikerta: 285
eISSN: 1090-2651
DOI: https://doi.org/10.1016/j.ic.2022.104883
Verkko-osoite: https://doi.org/10.1016/j.ic.2022.104883
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/175103989
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.
Ladattava julkaisu This is an electronic reprint of the original article. |