Article (Scientific journals)
Extensions and restrictions of Wythoff's game preserving its P positions
Duchêne, Eric; Fraenkel, Aviezri; Nowakowski, Richard et al.
2010In Journal of Combinatorial Theory. Series A, 117, p. 545-567
Peer Reviewed verified by ORBi
 

Files


Full Text
dfnr_last.pdf
Author preprint (253.64 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Wythoff's game; game theory; morphic word; shape-symmetry; automatic sequence; fibonacci numeration system
Abstract :
[en] We consider extensions and restrictions of Wythoff's game having exactly the same set of P positions as the original game. No strict subset of rules give the same set of P positions. On the other hand, we characterize all moves that can be adjoined while preserving the original set of P positions. Testing if a move belongs to such an extended set of rules is shown to be doable in polynomial time. Many arguments rely on the infinite Fibonacci word, automatic sequences and the corresponding number system. With these tools, we provide new two-dimensional morphisms generating an infinite picture encoding respectively P positions of Wythoff's game and moves that can be adjoined.
Disciplines :
Mathematics
Author, co-author :
Duchêne, Eric
Fraenkel, Aviezri
Nowakowski, Richard
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Extensions and restrictions of Wythoff's game preserving its P positions
Publication date :
March 2010
Journal title :
Journal of Combinatorial Theory. Series A
ISSN :
0097-3165
Publisher :
Academic Press
Volume :
117
Pages :
545-567
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 29 July 2009

Statistics


Number of views
153 (19 by ULiège)
Number of downloads
2 (2 by ULiège)

Scopus citations®
 
41
Scopus citations®
without self-citations
28
OpenCitations
 
35

Bibliography


Similar publications



Contact ORBi