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 [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 | ||||||||||||||

| ||||||||||||||

All documents in ORBi are protected by a user license.