A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Automatic winning shifts




TekijätPeltomäki Jarkko, Salo Ville

KustantajaElsevier Inc.

Julkaisuvuosi2022

JournalInformation and Computation

Tietokannassa oleva lehden nimiInformation and Computation

Artikkelin numero104883

Vuosikerta285

eISSN1090-2651

DOIhttps://doi.org/10.1016/j.ic.2022.104883

Verkko-osoitehttps://doi.org/10.1016/j.ic.2022.104883

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/175103989


Tiivistelmä

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.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 15:31