A1 Refereed original research article in a scientific journal

Automatic winning shifts




AuthorsPeltomäki Jarkko, Salo Ville

PublisherElsevier Inc.

Publication year2022

JournalInformation and Computation

Journal name in sourceInformation and Computation

Article number104883

Volume285

eISSN1090-2651

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

Web address https://doi.org/10.1016/j.ic.2022.104883

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/175103989


Abstract

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.


Downloadable publication

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