On winning shifts of marked uniform substitutions

Peltomäki, Jarkko; Salo, Ville

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 1-2, pp. 51-66.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

The second author introduced with I. Törmä a two-player word-building game [Fund. Inform. 132 (2014) 131–152]. The game has a predetermined (possibly finite) choice sequence ${\alpha }_1,{\alpha }_2$ of integers such that on round , α of integers such that on round $n$ the player $A$ chooses a subset $S_n$ chooses a subset of size chooses a subset ${\alpha }_n$ of some fixed finite alphabet and the player $B$ picks a letter from the set $S_n$. The outcome is determined by whether the word obtained by concatenating the letters $B$ picked lies in a prescribed target set $X$ (a win for player $A$) or not (a win for player $B$). Typically, we consider $X$ to be a subshift. The winning shift $W\left(X\right)$ of a subshift $X$ is defined as the set of choice sequences for which $A$ has a winning strategy when the target set is the language of $X$. The winning shift $W\left(X\right)$ mirrors some properties of $X$. For instance, $W\left(X\right)$ and $X$ have the same entropy. Virtually nothing is known about the structure of the winning shifts of subshifts common in combinatorics on words. In this paper, we study the winning shifts of subshifts generated by marked uniform substitutions, and show that these winning shifts, viewed as subshifts, also have a substitutive structure. Particularly, we give an explicit description of the winning shift for the generalized Thue–Morse substitutions. It is known that $W\left(X\right)$ and $X$ have the same factor complexity. As an example application, we exploit this connection to give a simple derivation of the first difference and factor complexity functions of subshifts generated by marked substitutions. We describe these functions in particular detail for the generalized Thue–Morse substitutions.

[1] J.-P. Allouche and J. Shallit, Sums of digits, overlaps, and palindromes. Discret. Math. Theor. Comput. Sci. 4 (2000) 1–10 | MR | Zbl

[2] J.-P. Allouche and J. Shallit, Automatic . Cambridge University Press (2003)

[3] R.P. Anstee, L. Rónyai and A. Sali, Shattering news. Graphs Comb. 18 (2002) 59–73 | DOI | MR | Zbl

[4] L. Balková, Factor frequencies in generalized Thue–Morse words. Kybernetika 48 (2012) 371–385 | MR | Zbl

[5] S. Brlek, Enumeration of factors in the Thue–Morse word. Discret Appl. Math. 24 (1989) 83–96 | DOI | MR | Zbl

[6] A. De Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theor. Comput. Sci. 63 (1989) 333–348 | DOI | MR | Zbl

[7] A. Frid, On uniform D0L words, 15th Symposium on Theoretical Aspects of Computer Science. In Vol. 1373, Lecture Notes in Computer Science. Springer (1998) 544–554 | MR

[8] D. Gale and F.M. Stewart, Infinite games with perfect information in Contributions to the Theory of Games. In Vol. II of Annals of Mathematics Studies. Princeton University Press (1953) 245–266 | MR | Zbl

[9] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and Its Applications. Addison-Wesley, Boston (1983) | MR | Zbl

[10] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (2002) | Zbl

[11] B. Mossé, Puissances de mots et reconnaissabilité des points fixes d’une substitution. Theor. Comput. Sci. 99 (1992) 327–334 | DOI | MR | Zbl

[12] B. Mossé, Reconnaissabilité des substututions et complexité des suites automatiques. Bull. Soc. Math. France 124 (1996) 329–346 | DOI | Numdam | MR | Zbl

[13] J. Peltomäki and V. Salo, On winning shifts of generalized Thue–Morse substitutions, in Proceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics, edited by J. Karhumäki, Yu. Matiyasevich and A. Saarela. TUCS Lecture Notes No. 26. Turku Center for Computer Science (2017) 123–132.

[14] S. Štarosta Generalized Thue–Morse words and palindromic richness. Kybernetika 48 (2012) 361–370 | MR | Zbl

[15] I. Törmä and V. Salo, Playing with subshifts. Fundam. Inform. 132 (2014) 131–152 | DOI | MR | Zbl

[16] J. Tromp and J. Shallit, Subword complexity of the generalized Thue-Morse word. Inform. Process. Lett. 54 (1995) 313–316 | DOI | MR | Zbl