Reference : Deciding game invariance
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/205740
Deciding game invariance
English
Duchêne, Eric []
Parreau, Aline []
Rigo, Michel mailto [Université de Liège > Département de mathématique > Mathématiques discrètes >]
2017
Information & Computation
Academic Press
253
127-142
Yes (verified by ORBi)
International
0890-5401
1090-2651
San Diego
CA
[en] Combinatorial game ; Impartial game ; Decision problem ; First-order logic ; Recognizable sets of integers
[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.
Researchers
http://hdl.handle.net/2268/205740
10.1016/j.ic.2017.01.010

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
final.pdfAuthor postprint286.14 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.