Automatic winning shifts

Abstract

<p>To each one-dimensional subshift X, we may associate a winning shift <i>W(X)</i> which arises from a combinatorial game played on the language of X. Previously it has been studied what properties of X does <i>W(X)</i> inherit. For example, X and <i>W(X)</i> have the same factor complexity and if X is a sofic subshift, then <i>W(X)</i> is also sofic. In this paper, we develop a notion of automaticity for <i>W(X)</i>, that is, we propose what it means that a vector representation of <i>W(X)</i> is accepted by a finite automaton.<br></p><p>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 <i>W(X)</i> (which follows from X having sublinear factor complexity), then <i>W(X)</i> 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.<br></p>