Playing with Subshifts

• Autorzy: Salo V. , Törmä I.

Identyfikatory

DOI

10.3233/FI-2014-1037

• Języki publikacji: EN

Abstrakty

EN

We study the class of word-building games, where two players pick letters from a finite alphabet to construct a finite or infinite word. The outcome is determined by whether the resulting word lies in a prescribed set (a win for player A) or not (a win for player B). We focus on symbolic dynamical games, where the target set is a subshift. We investigate the relation between the target subshift and the set of turn orders for which A has a winning strategy.

Słowa kluczowe

EN

subshift; games; perfect information; entropy

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 1
• Strony: 131--152
• Opis fizyczny: Bibliogr. 10 poz., rys., wykr.

Twórcy

autor

Salo V.

• TUCS – Turku Centre for Computer Science, Finland University of Turku, Finland

autor

Törmä I.

• TUCS – Turku Centre for Computer Science, Finland University of Turku, Finland

Bibliografia

• [1] Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28: 114–133, January 1981.
• [2] F. Durand, B. Host, and C. Skau. Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theory Dynam. Systems, 19(4): 953–993, 1999.
• [3] David Gale and F. M. Stewart. Infinite games with perfect information. In Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, pages 245–266. Princeton University Press, Princeton, N. J., 1953.
• [4] Douglas Lind and Brian Marcus. An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995.
• [5] M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2002.
• [6] Erez Louidor, Brian Marcus, and Ronnie Pavlov. Independence entropy of Zd-shift spaces. Acta Applicandae Mathematicae, pages 1–21, 2013.
• [7] Donald A. Martin. Borel determinacy. Ann. of Math. (2), 102(2): 363–371, 1975.
• [8] Brigitte Mossé. Puissances de mots et reconnaissabilité des points fixes d’une substitution. Theoret. Comput. Sci., 99(2): 327–334, 1992.
• [9] Wesley Pegden. Highly nonrepetitive sequences: winning strategies from the local lemma. Random Structures Algorithms, 38(1-2): 140–161, 2011.
• [10] A. M. Shur. Growth of power-free languages: numerical and asymptotic bounds. Dokl. Akad. Nauk, 432(3): 315–317, 2010.