Automatic winning shifts (Q2672264)

Start with a combinatorial game played as follows. Let \(X\) be a target set of words of length \(n\) over an alphabet \(A\) and a sequence \(\alpha_1,\ldots,\alpha_n\) of non-negative integers less than \(|A|\). On each round \(i\in\{1,\ldots,n\}\), Alice first selects a subset of \(A\) of size \(\alpha_i+1\), then Bob picks a letter from this subset. At the end of the \(n\) rounds, a word has been built. If it belongs to \(X\), Alice wins, otherwise, Bob wins. Let \(W(X)\) be the set of choice sequences for which Alice has a winning strategy. This game can in a natural way be extended to infinitely many turns: if \(X\) is a subshift, then \(W(X)\) also is. The first properties of these shifts were studied by Törmä and Salo. The aim of this paper is to study the structure of the winning shift \(W(X)\) of a subshift \(X\) generated by an automatic word. The authors consider the general framework of an abstract numeration system \(S\) introduced by Lecomte and Rigo. An infinite word \(x\) is \(S\)-automatic if there exists a finite automaton \(\mathcal{A}\) such that the \(n\)th term of \(x\) is the output of \(\mathcal{A}\) fed with the representation of \(n\) in the system \(S\). One of the main results states that if \(S\) is addable, i.e., if the addition relation within \(S\) is rational, and if \(X\) is a subshift generated by an \(S\)-automatic word with sublinear factor complexity, then its winning shift \(W(X)\) is \(S\)-codable, i.e., it is an infinite word over \(\mathbb{N}\) whose support, represented in \(S\), can be recognized by a finite automaton. In particular, properties of the class of \(S\)-codable subshifts are also considered. As a corollary, the authors consider the setting of numeration systems based on a Pisot number, which are known to be addable. For instance, the Fibonacci system belongs to this category. Having constructive proofs depending on the description of \(X\), the authors determine the automaton for the winning shifts of the subshifts generated by some well-known 2-automatic words: the Thue-Morse word, the regular paperfolding word, the Rudin-Shapiro word, and the period-doubling word.