Automatic winning shifts

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.

Authors

• Jarkko Peltomäki
• Ville Salo

Keywords

• Winning shift
• Combinatorial game
• Abstract numeration system
• Automatic sequence
• Regular language
• Sofic shift