Deciding game invariance

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

doi:10.1016/j.ic.2017.01.010

Download

Article (Scientific journals)

Deciding game invariance

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

2017 • In Information and Computation, 253, p. 127-142

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/205740

DOI
10.1016/j.ic.2017.01.010

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

final.pdf

Author postprint (293.01 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Combinatorial game; Impartial game; Decision problem; First-order logic; Recognizable sets of integers

Abstract :

[en] In a preivous paper, Duchêne and Rigo 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 P -positions is relevant. In particular, it was recently proved by Larsson et al. 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.

Disciplines :

Computer science
Mathematics

Author, co-author :

Duchêne, Eric

Parreau, Aline

Rigo, Michel ; Université de Liège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Deciding game invariance

Publication date :

2017

Journal title :

Information and Computation

ISSN :

0890-5401

eISSN :

1090-2651

Publisher :

Academic Press, San Diego, United States - California

Volume :

253

Pages :

127-142

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 23 January 2017

Statistics

Number of views

73 (3 by ULiège)

Number of downloads

122 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Ho, N.B., Two variants of Wythoff's game preserving its P-positions (2012) J. Comb. Theory, Ser. A, 119 (6), pp. 1302-1314
Berthé, V., Rigo, M., (2010) Combinatorics, Automata and Number Theory, Encycl. Math. Appl., 135. , Cambridge University Press Cambridge
Bruyère, V., Hansel, G., Bertrand numeration systems and recognizability (1997) Theor. Comput. Sci., 181 (1), pp. 17-43
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R., Logic and p-recognizable sets of integers (1994) Bull. Belg. Math. Soc. Simon Stevin, 1 (2), pp. 191-238
Büchi, J.R., Weak second-order arithmetic and finite automata (1960) Z. Math. Log. Grundl. Math., 6, pp. 66-92
Carpi, A., Maggi, C., On synchronized sequences and their separators (2001) Theor. Inform. Appl., 35 (6), pp. 513-524. , (2002)
Cassaigne, J., Duchêne, E., Rigo, M., Nonhomogeneous Beatty sequences leading to invariant games (2016) SIAM J. Discrete Math., 30, pp. 1798-1829
Du, C.F., Mousavi, H., Schaeffer, L., Shallit, J., Decision algorithms for Fibonacci-automatic words, I: basic results (2016) RAIRO Theor. Inform. Appl., 50 (1), pp. 39-66
Duchêne, E., Fraenkel, A.S., Nowakowski, R.J., Rigo, M., Extensions and restrictions of Wythoff's game preserving its P positions (2010) J. Comb. Theory, Ser. A, 117 (5), pp. 545-567
Duchêne, E., Rigo, M., A morphic approach to combinatorial games: the Tribonacci case (2008) Theor. Inform. Appl., 42 (2), pp. 375-393
Duchêne, E., Rigo, M., Pisot unit combinatorial games (2008) Monatshefte Math., 155 (3-4), pp. 217-249
Duchêne, E., Rigo, M., Invariant games (2010) Theor. Comput. Sci., 411 (34-36), pp. 3169-3180
Fraenkel, A.S., Systems of numeration (1985) Am. Math. Mon., 92 (2), pp. 105-114
Fraenkel, A.S., Heap games, numeration systems and sequences (1998) Ann. Comb., 2 (3), pp. 197-210
Fraenkel, A.S., Aperiodic subtraction games (2011) Electron. J. Comb., 18 (2), pp. 19-31
Fraenkel, A.S., The rat game and the mouse game (2015) Games of No Chance 4, Math. Sci. Res. Inst. Publ., 63. , R.J. Nowakowski
Fraenkel, A.S., The Raleigh game (2007) Integers, 7, p. #13. , 11 pp
Fraenkel, A.S., Larsson, U., Take-away games on Beatty's theorem and the notion of invariance preprint
Frougny, C., Representations of numbers and finite automata (1992) Math. Syst. Theory, 25 (1), pp. 37-60
Frougny, C., On the sequentiality of the successor function (1997) Inf. Comput., 139 (1), pp. 17-38
Goč, D., Henshall, D., Shallit, J., Automatic theorem-proving in combinatorics on words (2012) CIAA 2012, Lect. Notes Comput. Sci., 7381, pp. 180-191. , N. Moreira R. Reis Springer-Verlag
Goč, D., Rampersad, N., Rigo, M., Salimov, P., On the number of abelian bordered words (with an example of automatic theorem-proving) (2014) Internat. J. Found. Comput. Sci., 25 (8), pp. 1097-1110
Larsson, U., Hegarty, P., Fraenkel, A.S., Invariant and dual subtraction games resolving the Duchêne–Rigo conjecture (2011) Theor. Comput. Sci., 412, pp. 729-735
Larsson, U., Wästlund, J., From heaps of matches to the limits of computability (2013) Electron. J. Comb., 20 (3), p. #P41
Lothaire, M., Combinatorics on Words (1997) Cambridge Math. Lib., , corrected reprint of the 1983 original Cambridge University Press Cambridge
Mousavi, H., Automatic theorem proving in Walnut arXiv:1603.06017
Mousavi, H., Shallit, J., Mechanical Proofs of Properties of the Tribonacci Word (2015) Lect. Notes Comput. Sci., 9304, pp. 170-190. , Springer Cham
Rigo, M., Maes, A., More on generalized automatic sequences (2002) J. Autom. Lang. Comb., 7, pp. 351-376
Rigo, M., Formal Languages, Automata and Numeration Systems (2014), ISTE/John Wiley & Sons, Inc. London/Hoboken, NJ
Sakarovitch, J., Elements of Automata Theory (2009), Cambridge University Press Cambridge