Article (Scientific journals)
Deciding game invariance
Duchêne, Eric; Parreau, Aline; Rigo, Michel
2017In Information and Computation, 253, p. 127-142
Peer Reviewed verified by ORBi
 

Files


Full Text
final.pdf
Author postprint (293.01 kB)
Download

All documents in ORBi are protected by a user license.

Send to



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
57 (3 by ULiège)
Number of downloads
114 (2 by ULiège)

Scopus citations®
 
3
Scopus citations®
without self-citations
3
OpenCitations
 
2

Bibliography


Similar publications



Contact ORBi