Eric Duchêne ; Victor Marsault ; Aline Parreau ; Michel Rigo - Taking-and-merging games as rewrite games

dmtcs:5200 - Discrete Mathematics & Theoretical Computer Science, September 23, 2020, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-5
Taking-and-merging games as rewrite gamesArticle

Authors: Eric Duchêne ; Victor Marsault ORCID; Aline Parreau ; Michel Rigo

    This work is a contribution to the study of rewrite games. Positions are finite words, and the possible moves are defined by a finite number of local rewriting rules. We introduce and investigate taking-and-merging games, that is, where each rule is of the form a^k->epsilon. We give sufficient conditions for a game to be such that the losing positions (resp. the positions with a given Grundy value) form a regular language or a context-free language. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games. Finally we show that more general rewrite games quickly lead to undecidable problems. Namely, it is undecidable whether there exists a winning position in a given regular language, even if we restrict to games where each move strictly reduces the length of the current position. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games.


    Volume: vol. 22 no. 4
    Published on: September 23, 2020
    Accepted on: August 3, 2020
    Submitted on: February 21, 2019
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Discrete Mathematics,Computer Science - Computer Science and Game Theory,Mathematics - Combinatorics
    Funding:
      Source : OpenAIRE Graph
    • Games and graphs; Funder: French National Research Agency (ANR); Code: ANR-14-CE25-0006

    Consultation statistics

    This page has been seen 431 times.
    This article's PDF has been downloaded 228 times.