• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Winning Shifts of Generalized Thue-Morse Substitutions

Jarkko Peltomäki, Ville Salo, On Winning Shifts of Generalized Thue-Morse Substitutions. In: Juhani Karhumäki, Yuri Matiyasevich, Aleksi Saarela (Eds.), Proceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics, TUCS Lecture Notes 26, 123–132, TUCS, 2017.

Abstract:

The second author introduced with I. Törmä a two-player word-building game [Playing with Subshifts, Fund. Inform. 132 (2014), 131--152]. The game has a predetermined (possibly finite) choice sequence $\alpha_1$, $\alpha_2$, $\ldots$ of integers such that on round $n$ the player $A$ chooses a subset $S_n$ of size $\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$).

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 factor complexity. In this paper, we completely describe the winning shifts of subshifts generated by the generalized Thue-Morse substitutions and show that they have a substitutive structure. We show how the description can be used to derive their factor complexity functions.

BibTeX entry:

@INPROCEEDINGS{inpPeSa17a,
  title = {On Winning Shifts of Generalized Thue-Morse Substitutions},
  booktitle = {Proceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics},
  author = {Peltomäki, Jarkko and Salo, Ville},
  volume = {26},
  series = {TUCS Lecture Notes},
  editor = {Karhumäki, Juhani and Matiyasevich, Yuri and Saarela, Aleksi},
  publisher = {TUCS},
  pages = {123–132},
  year = {2017},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication