A4 Vertaisarvioitu artikkeli konferenssijulkaisussa

On winning shifts of generalized Thue-Morse substitutions




TekijätPeltomäki Jarkko, Salo Ville

ToimittajaKarhumäki Juhani, Matiyasevich Yuri, Saarela Aleksi

Konferenssin vakiintunut nimiRussian Finnish Symposium on Discrete Mathematics

Julkaisuvuosi2017

JournalTUCS Lecture Notes

Kokoomateoksen nimiProceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics

Sarjan nimiTUCS Lecture Notes

Numero sarjassa26

Aloitussivu123

Lopetussivu132

ISBN978-952-12-3547-4

ISSN1797-8823

Verkko-osoitehttp://www.utupub.fi/handle/10024/143322

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/26970008


Tiivistelmä

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$). 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. It is known that $W(X)$ and $X$ have the same factor complexity. 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.



Last updated on 2024-26-11 at 14:12