| Summary: | 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.
|
|---|