×
Duchêne, Eric; Parreau, Aline; Rigo, Michel

Deciding game invariance. (English) Zbl 1410.91126

Inf. Comput. 253, Part 1, 127-142 (2017).
Summary: In a previous paper, the first and the third author [Theor. Comput. Sci. 411, No. 34–36, 3169–3180 (2010; Zbl 1198.91051)] introduced the notion of invariance for take-away games on heaps. Roughly speaking, these are games whose rulesets do not depend on the position. Given a sequence \(S\) of positive tuples of integers, the question of whether there exists an invariant game having \(S\) as set of \(\mathcal{P}\)-positions is relevant. In particular, it was recently proved by U. Larsson et al. [Theor. Comput. Sci. 412, No. 8–10, 729–735 (2011; Zbl 1237.91062)] that if \(S\) is a pair of complementary Beatty sequences, then the answer to this question is always positive. In this paper, we show that for a fairly large set of sequences (expressed by infinite words), the answer to this question is decidable.

Cited in 2 Documents

MSC:

91A46 Combinatorial games
68R15 Combinatorics on words

Keywords:

combinatorial game; impartial game; decision problem; first-order logic; recognizable sets of integers

Citations:

Zbl 1198.91051; Zbl 1237.91062

Software:

Walnut
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Ho, N. B., Two variants of Wythoff’s game preserving its \(P\)-positions, J. Comb. Theory, Ser. A, 119, 6, 1302-1314 (2012) · Zbl 1242.91033
[2] (Berthé, V.; Rigo, M., Combinatorics, Automata and Number Theory. Combinatorics, Automata and Number Theory, Encycl. Math. Appl., vol. 135 (2010), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 1197.68006
[3] Bruyère, V.; Hansel, G., Bertrand numeration systems and recognizability, Theor. Comput. Sci., 181, 1, 17-43 (1997) · Zbl 0957.11015
[4] Bruyère, V.; Hansel, G.; Michaux, C.; Villemaire, R., Logic and \(p\)-recognizable sets of integers, Bull. Belg. Math. Soc. Simon Stevin, 1, 2, 191-238 (1994) · Zbl 0804.11024
[5] Büchi, J. R., Weak second-order arithmetic and finite automata, Z. Math. Log. Grundl. Math., 6, 66-92 (1960) · Zbl 0103.24705
[6] Carpi, A.; Maggi, C., On synchronized sequences and their separators, Theor. Inform. Appl., 35, 6, 513-524 (2001), (2002) · Zbl 1003.68064
[7] Cassaigne, J.; Duchêne, E.; Rigo, M., Nonhomogeneous Beatty sequences leading to invariant games, SIAM J. Discrete Math., 30, 1798-1829 (2016) · Zbl 1419.11047
[8] Du, C. F.; Mousavi, H.; Schaeffer, L.; Shallit, J., Decision algorithms for Fibonacci-automatic words, I: basic results, RAIRO Theor. Inform. Appl., 50, 1, 39-66 (2016) · Zbl 1366.68226
[9] Duchêne, E.; Fraenkel, A. S.; Nowakowski, R. J.; Rigo, M., Extensions and restrictions of Wythoff’s game preserving its \(P\) positions, J. Comb. Theory, Ser. A, 117, 5, 545-567 (2010) · Zbl 1185.91061
[10] Duchêne, E.; Rigo, M., A morphic approach to combinatorial games: the Tribonacci case, Theor. Inform. Appl., 42, 2, 375-393 (2008) · Zbl 1143.91314
[11] Duchêne, E.; Rigo, M., Pisot unit combinatorial games, Monatshefte Math., 155, 3-4, 217-249 (2008) · Zbl 1185.68504
[12] Duchêne, E.; Rigo, M., Invariant games, Theor. Comput. Sci., 411, 34-36, 3169-3180 (2010) · Zbl 1198.91051
[13] Fraenkel, A. S., Systems of numeration, Am. Math. Mon., 92, 2, 105-114 (1985) · Zbl 0568.10005
[14] Fraenkel, A. S., Heap games, numeration systems and sequences, Ann. Comb., 2, 3, 197-210 (1998) · Zbl 0942.91015
[15] Fraenkel, A. S., Aperiodic subtraction games, Electron. J. Comb., 18, 2, 19-31 (2011) · Zbl 1237.91061
[16] Fraenkel, A. S., The rat game and the mouse game, (Nowakowski, R. J., Games of No Chance 4. Games of No Chance 4, Math. Sci. Res. Inst. Publ., vol. 63 (2015)) · Zbl 1380.91043
[17] Fraenkel, A. S., The Raleigh game, Integers, 7, #13 (2007), 11 pp · Zbl 1178.91037
[19] Frougny, Ch., Representations of numbers and finite automata, Math. Syst. Theory, 25, 1, 37-60 (1992) · Zbl 0776.11005
[20] Frougny, Ch., On the sequentiality of the successor function, Inf. Comput., 139, 1, 17-38 (1997) · Zbl 0892.68065
[21] Goč, D.; Henshall, D.; Shallit, J., Automatic theorem-proving in combinatorics on words, (Moreira, N.; Reis, R., CIAA 2012. CIAA 2012, Lect. Notes Comput. Sci., vol. 7381 (2012), Springer-Verlag), 180-191 · Zbl 1297.68215
[22] Goč, D.; Rampersad, N.; Rigo, M.; Salimov, P., On the number of abelian bordered words (with an example of automatic theorem-proving), Internat. J. Found. Comput. Sci., 25, 8, 1097-1110 (2014) · Zbl 1309.68162
[23] Larsson, U.; Hegarty, P.; Fraenkel, A. S., Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture, Theor. Comput. Sci., 412, 729-735 (2011) · Zbl 1237.91062
[24] Larsson, U.; Wästlund, J., From heaps of matches to the limits of computability, Electron. J. Comb., 20, 3, #P41 (2013) · Zbl 1295.91024
[25] Lothaire, M., Combinatorics on Words, Cambridge Math. Lib. (1997), Cambridge University Press: Cambridge University Press Cambridge, corrected reprint of the 1983 original · Zbl 0874.20040
[26] Mousavi, H., Automatic theorem proving in Walnut
[27] Mousavi, H.; Shallit, J., Mechanical Proofs of Properties of the Tribonacci Word, Lect. Notes Comput. Sci., vol. 9304, 170-190 (2015), Springer: Springer Cham · Zbl 1350.68218
[28] Rigo, M.; Maes, A., More on generalized automatic sequences, J. Autom. Lang. Comb., 7, 351-376 (2002) · Zbl 1033.68069
[29] Rigo, M., Formal Languages, Automata and Numeration Systems (2014), ISTE/John Wiley & Sons, Inc.: ISTE/John Wiley & Sons, Inc. London/Hoboken, NJ · Zbl 1326.68003
[30] Sakarovitch, J., Elements of Automata Theory (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1188.68177
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.