Automatic winning shifts

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.

28 pages, 5 figures, 1 table