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.

Kokoelmat

Rinnakkaistallenteet [19207]