Reference : Extensions and restrictions of Wythoff's game preserving its P-positions
 Document type : Scientific conferences in universities or research centers : Scientific conference in universities or research centers Discipline(s) : Physical, chemical, mathematical & earth Sciences : MathematicsEngineering, computing & technology : Computer science To cite this reference: http://hdl.handle.net/2268/100440
 Title : Extensions and restrictions of Wythoff's game preserving its P-positions Language : English Author, co-author : Rigo, Michel [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >] Publication date : 21-Oct-2011 Audience : National Event name : Séminaire de l'équipe "Automates et applications", LIAFA (Chevaleret) Event place (city) : Paris Keywords : [en] Combinatorial game ; Fibonacci word ; Morphism Abstract : [en] Wythoff's game is a century old classical two players combinatorial game. When studying this game, Beatty sequences associated with the Golden Ratio, syntactical properties of the representations of integers in the Fibonacci or Zeckendorf numeration system and the morphic Fibonacci word appear naturally in characterizations of its P-positions. Recall that whatever is the move played from a P-position, the other player has a winning strategy. Contrarily to the usual approach where one defines a new game by a set of rules and then tries to characterize the corresponding set of P-positions, our motivations are to proceed the other way around: keep the original set of P-positons while changing the rules. We consider extensions and restrictions of Wythoff's game having exactly the same set of P-positions as the original game. Our results are the following one: no strict subset of rules gives 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 done in polynomial time. In this talk, we won't consider many game theoretical aspects (but we will recall some basic facts on combinatorial games). We focus mainly on the role played by numeration systems, regular languages and bidimensional words generated by substitutions/morphisms. Indeed, games like this one provide nice interaction between combinatorics on words and combinatorial game theory. For instance, the set of P-positions of Wythoff's game are "coded" by the infinite Fibonacci word. Therefore, many arguments rely on this word, on automatic sequences and on the corresponding numeration systems. With these tools, we provide new bidimensional (shape-symmetric in the sense of Arnaud Maes) morphisms generating an infinite picture encoding respectively P-positions of Wythoff's game and moves that can be adjoined preserving the same set of P-positions. Permalink : http://hdl.handle.net/2268/100440 Other URL : http://orbi.ulg.ac.be/handle/2268/17591 Commentary : Joint work with E. Duchene, A. Fraenkel, R. Nowakowski, E. Duchêne, A. S. Fraenkel, R. J. Nowakowski, M. Rigo, Extensions and restrictions of Wythoff's game preserving its P-positions. J. Combin. Theory Ser. A 117 (2010), no. 5, 545–-567

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access