Playing with Subshifts

Issue title: Russian-Finnish Symposium in Discrete Mathematics

Article type: Research Article

Authors: Salo, Ville | Törmä, Ilkka

Affiliations: TUCS – Turku Centre for Computer Science, Finland; University of Turku, Finland. [email protected], [email protected]

Note: [] Address for correspondence: TUCS – Turku Centre for Computer Science, University of Turku, Finland

Abstract: 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.

Keywords: subshifts, games, perfect information, entropy

DOI: 10.3233/FI-2014-1037

Journal: Fundamenta Informaticae, vol. 132, no. 1, pp. 131-152, 2014