RAIRO-Theor. Inf. Appl.
Volume 53, Number 1-2, January–June 2019
|Page(s)||51 - 66|
|Published online||15 January 2019|
On winning shifts of marked uniform substitutions
Turku Centre for Computer Science TUCS,
2 Department of Mathematics and Statistics, University of Turku, Turku, Finland
* Corresponding author: firstname.lastname@example.org
Accepted: 31 October 2018
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 α1, α2, … of integers such that on round n the player A chooses a subset Sn of size αn of some fixed finite alphabet and the player B picks a letter from the set Sn. 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(X) 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(X) mirrors some properties of X. For instance, W(X) 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(X) 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.
Mathematics Subject Classification: 68R15
Key words: Two-player game, winning shift / marked substitution / factor complexity / generalized Thue–Morse word
© EDP Sciences, 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.