Geodesic
Taking-and-merging games as rewrite games
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 4

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2020_22_4_a5,
     author = {Duch\^ene, Eric and Marsault, Victor and Parreau, Aline and Rigo, Michel},
     title = {Taking-and-merging games as rewrite games},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-4-5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-5/}
}
TY  - JOUR
AU  - Duchêne, Eric
AU  - Marsault, Victor
AU  - Parreau, Aline
AU  - Rigo, Michel
TI  - Taking-and-merging games as rewrite games
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-5/
DO  - 10.23638/DMTCS-22-4-5
LA  - en
ID  - DMTCS_2020_22_4_a5
ER  - 
%0 Journal Article
%A Duchêne, Eric
%A Marsault, Victor
%A Parreau, Aline
%A Rigo, Michel
%T Taking-and-merging games as rewrite games
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-5/
%R 10.23638/DMTCS-22-4-5
%G en
%F DMTCS_2020_22_4_a5
Duchêne, Eric; Marsault, Victor; Parreau, Aline; Rigo, Michel. Taking-and-merging games as rewrite games. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 4. doi: 10.23638/DMTCS-22-4-5

Cité par Sources :