1 Introduction
Waldmann introduces general rewrite games as follows [9]. Let be a finite alphabet, i.e., a finite set of symbols. We let denote the set of finite words over . The empty word is denoted by . A rewrite system is given by a (finite) set of rules, called reductions, of the form . The latter rule can be applied to the word , where we replace one occurrence of by and we write . Starting from a word, also called ground term, and a terminating^{1}^{1}1This condition ensures that no infinite sequence of reduction may occur. Otherwise stated, we are dealing with games having an acyclic gamegraph. rewrite system , two players apply alternatively an reduction of their choice to get a sequence until no reduction can be applied. The first player unable to apply an reduction, because is in normal form (i.e., irreducible), loses the game ( is called a final position of the game).
Rewrite games belong to the family of impartial combinatorial games, i.e., games having 2 players moving alternately with perfect information. Both players always have the same available moves and the first one unable to move loses. A complete definition can be found in [6]. Takingandbreaking games are famous examples of such games, played on several piles of tokens, where a general move consists in decreasing the size of a pile and then splitting it into several smaller piles. A major issue when studying combinatorial games is the computation of the outcome. An impartial combinatorial game position has outcome if the player who starts has a winning strategy, and otherwise.
Octal games (i.e., takingandbreaking games where piles of tokens can be split into at most two piles and the moves are coded by integers less than or equal to written in base , see [6] for a formal definition) is a wellknown family of combinatorial games that can be described as rewrite games. This is, in particular, also the case for subtraction games (where no breaking of a pile is allowed). If we have piles of token with respectively tokens, then a position in such a game can be coded by the word over a twoletter alphabet
The ’s play the role of separators between piles of ’s and one has to carefully choose the convenient reductions to code the game of interest, see [9, Prop. 3].
Example 1.
Let us consider the game over the alphabet , with the rewrite system . An example of sequence of play for this game, starting from the ground term , is
In this example, four moves have been played, hence the second player wins the game. Note that this game exactly corresponds to the octal game where a player can remove one token of a pile (possibly emptying it) or can remove two tokens from a pile and possibily emptying it or dividing the remaining pile into two piles.
In particular, one can reformulate a famous conjecture [2]
in combinatorial game theory (also known as Guy’s conjecture): do all finite octal games have an eventually periodic Sprague–Grundy sequence?
Recall that for an impartial combinatorial game (with an acyclic gamegraph), the Grundy value (also called Sprague–Grundy value) of any position is recursively defined as the MeX (minimum excluded value) of the set of Grundy values of its options, with the convention that the MeX of the empty set is . For example, . If the Grundy value of a game is a major tool when playing on disjunctive sums of games, it also refines the notion of outcome. Indeed, game positions having a Grundy value equal to are exactly those of outcome .
In the current context, for an arbitrary terminating rewrite game, positions are words over a finite alphabet and we can associate a Grundy value with each word in . Hence the Grundy sequence of an octal game seen as a rewrite game is the sequence . Selecting all words in with a given Grundy value gives a language
i.e., a subset of . We say that is a Grundy language. Therefore, given a rewrite game , Lemma 2 (see [2]) gives a sufficient condition to determine the Grundy function of :
Lemma 2.
Given a rewrite game over an alphabet , if there exists a partition of , with an index set or , such that:

for all , every move from words in leads to a word not in (stability property),

for all pair with , from every word in , there exists a move leading to a word in (absorption property),
then, for all , we have .
In his paper [9], Waldmann proves the following result that builds a correspondence between the periodicity of octal games and the regularity of the corresponding languages .
Theorem 3 (Waldmann, 2002).
The Grundy sequence of an octal game is eventually periodic if and only if it has only finitely many nonempty Grundy languages , all of which are regular languages.
This nice result translates the notion of periodicity of a takingandbreaking game into the context of rewrite games. Therefore, the question of the regularity of rewrite games becomes paramount. This leads to the general open question: which rewrite games have Grundy values bounded by a constant and such that all the languages are regular? The famous conjecture of Guy [2] claims that every octal game has its Grundy sequence that is eventually periodic.
In what follows, we will assume that the reader is familiar with basic results about formal languages. We refer the reader to [3] for a general reference.
We let (resp. ) denote the number of (resp. ) occurring in the word .
In addition to octal games, some other wellknown games have also been considered in the context of rewrite games. It is for example the case of Pegsolitaire [4, 5], where is of the form .
In Pegsolitaire, it has been proved that on one dimensional boards, the set of solvable configurations forms a regular language. In the 2player version of the game, called duotaire, where series of hops can be done in a single move, neither the nor the positions form a regular nor even a contextfree language. Another example of a combinatorial game seen as a rewrite game is the game clobber [1], played over a letter alphabet with .
Takingandmerging games
In this paper, we consider a family of rewrite games over a twoletter alphabet, say , where any reduction rule of is either of the form or for some . In a certain way, this family allows us to model a new kind of pile games, where taking moves are combined with merging ones. For example, by following Waldmann’s description of octal games with a rewrite system, playing from the word leads to and can be seen as a merging of the piles and .
From now on and for the sake of notation, we will omit the reduction to in the description of the rewrite system. In other words, the games considered here will be denoted by a set , where the and are positive integers.
We now consider a first example of such a takingandmerging game. Using a convenient invariant (denoted by ) is a strategy that will appear in several proofs encountered in this paper.
Example 4.
Let us consider the game . We claim that the DFA (deterministic finite automaton) depicted in Figure 1 computes the Grundy function of : consider a word and start reading it from the initial state marked with an incoming arrow. Follow transitions reading the word letter by letter from left to right and look at the state reached when reading the last letter of . The states and correspond to the words of Grundy value , and the states and to those of Grundy value . First note that this is obviously true for the two final positions and . To prove this result, we define the following quantity for a given word :
One can first observe that for all , every word recognized by the state (for ) satisfies . To check this property, it suffices to consider each transition of the DFA and verify that changes accordingly. For example, reading a letter from the state increases by the value of , leading to the state , while reading a letter decreases by the value and leads to the state . Then, in order to prove that the DFA computes the Grundy values, by Lemma 2, it suffices to show that any move from a word recognized by a state (for ) leads to a word recognized by a state (for some ), and that any move from a word recognized by a state leads to some . These two properties can be easily checked by using the invariant :

By definition of , any move from a word such that leads to a word having , and conversely.

Any move satisfies the same property, as is modified by .
In view of such an example and according to Guy’s conjecture, it is natural to wonder whether the regularity of the languages would hold in the context of takingandmerging games. In Section 2, we will give a negative answer to this question, for games where both reductions and are forbidden. In addition, a proof of contextfreeness is given for simple instances of such games. In Section 3, we prove the regularity of several takingandmerging games. In particular, we exhibit DFAs computing their Grundy functions. Section 4 deals with a discussion about a result of Waldmann about the correlation between the regularity of , the other , and the number of Grundy values. The last section explains why we restricted our study to takingandmerging games: in the slightly more general settings of stronglyterminating rewrite games (i.e., where each move strictly decreases the length of the position), some problems become undecidable. Indeed, we show that then it is undecidable whether there exists a winning position in a given regular language of starting positions.
2 Not all games lead to regular languages
Our first result shows that Guy’s conjecture does not hold for takingandmerging games. More precisely, it states that, considering any takingandmerging game that excludes both reductions and , the set of positions is not a regular language.
2.1 Games with and
Theorem 5.
Let be the takingandmerging game , with and . If and , then the language of the position of is not regular.
Proof.
Let us show that the intersection of the set of positions of with the regular language , is not a regular language. More precisely, we prove by induction that an element of is a position if and only if .
If and , then there is only one valid move from position , and it leads to position , a final position. If and then is a final position, hence a position. Hence the claim is true if or .
Now, assume that and , then only one move is possible from , leading to position . From , again, only one move is possible, leading to position . Therefore, words and have the same outcome and by induction hypothesis is a position if and only if , which concludes the induction.
∎
2.2 Contextfreenes for
We have seen with Theorem 5 that the language made of positions is, in general, not regular. Nevertheless, when limited to a rewrite game with two reductions, we get the following result.
Theorem 6.
Let be positive integers. The takingandmerging game has only two Grundy values and the corresponding languages and are contextfree.
Proof.
It is quite obvious that the rewrite system is weakly confluent, that is, if and , then there exists a such that and (in our case, can be reached in at most one step). Since moreover, this rewriting system is terminating (i.e., there is no infinite chain of reductions), Newman’s Lemma [8] yields that the rewriting system is confluent or, stated otherwise, from any position can be reached a unique final position.
Let be a word and be the unique final position reachable from . If , , there exists such that and . This means that the reduction (resp. ) has been applied (resp. ) times in a sequence of reductions. Hence, playing the game starting from necessarily consists of moves. Consequently is a position (resp. a position) if and only if
is even (resp. odd)
To compute the Grundy value of a word, one just has to apply all the possible reductions in any order and count the parity of the number of applied reductions. This can be computed by a pushdown automata: reading the word from left to right, each time there are consecutive letters or consecutive letters , a reduction is simulated and the parity changed. Let us define more formally this pushdown automata. It has with three states: and an initial state . The stack alphabet is
where is a special symbol to represent the bottom of the stack. Transitions are of the form
where are states, is the symbol read by the automata, is the symbol that is popped from the top of the stack, is the word that is then pushed on the stack (with the usual convention that the leftmost symbol is on top of the stack). For , we have the transitions
For each transition, except the initial one where the stack is initialized with the special bottom symbol , observe that a symbol has to be popped from the stack. The stack is used as a memory of what has been read so far. If a contiguous block or has been detected, then one reduction is applied: the parity of the state is thus changed (see the last two transitions). When the word has been read, the reached state corresponds to the parity of the number of reductions that have been applied. We disregard the final content of the stack. ∎
Remark 7.
In the above result, when or is equal to , then the two languages and are actually regular. Indeed, the stack is not needed anymore. As an example, assume that and . Since the order of the moves is not important, one can assume that all the moves using the rule are first played. Then the word contains only letters and the rule is played until a position with is reached. Thus the number of moves from a starting position is and the Grundy value is the parity of this number. This can easily be computed by a DFA. The information about the number of that have been read modulo can be stored by states. We build a deterministic automaton with states to store the parity of the number of reductions that have been carried out. Reading a single switches this parity. In Figure 2, we have represented the DFA for the game . The value inside the states is the corresponding Grundy value.
3 Regularity of some games
In this section, we prove the regularity of some games of the form
By Remark 7, if the game has only two rules, , the game is trivial, there are only two Grundy values and the two corresponding languages and are regular. Therefore, in what follows, we consider games with at least three rules.
3.1 The game
In the game , due to the presence of the reductions and , the only irreducible word is and all words can be reduced to it. Let be a word. We need reductions of the form to get rid of the ’s. To get rid of all the ’s, since the reduction rules all involve an odd number of , the number of reductions to apply to eliminate the ’s has the same parity as . Hence, the number of reductions to apply to a word to obtain is even if and only if is even. We have a partition of into two sets depending on the parity of . Thanks to our discussion, we may apply Lemma 2. Hence, we get
and this language is easily seen to be regular. The same conclusion holds for .
Remark 8.
The same parity argument extends to a game whose set of rewriting rules contains , and any number of rules of the form and .
3.2 The game
In this section, we prove that for the game , the language of words of Grundy value is regular for any Grundy value and we explicitly give a DFA that computes the Grundy values.
Every word in can be uniquely written as
where and . For , let . With every word is thus associated a unique integer and the tuple . For , let be the number of blocks of ’s of size (modulo ). Finally, we define for every word the quantity
As an example, the word has , thus , and .
Lemma 9.
Let , the Grundy value of in the game is completly determined by , i.e.,
Proof.
We first prove that playing any rule changes the value of modulo 4. Let and consider each rule.

If the rule is played on a block , then decreases by 2 if and increases by 1 if .

If the rule is played, on a block , then increases by 2 if , by 1 if and decreases by 1 if .

Assume finally that the rule is played. Let and be the two blocks around the that will be removed. Table 1 gives, for every value of and , the variation of modulo .
0 1 2 0 2 2 2 1 2 1 1 2 2 1 2 Table 1: Variation of when the rule is applied to a between two blocks of ’s respectively of length and modulo 4. As an example, consider the case . Then one and two blocks of size (modulo ) are lost, decreasing the value of by , but we obtain a new block of size . Thus the total value decreases by which is congruent to modulo . Note that if (respectively ), then the number of blocks of of size and do not change modulo 3 and only one is removed, decreasing by the value .
We now prove that if , there is a move to with . If is odd, is also odd and in particular, there must be a block with . Then playing if or if on this block leads to a word with . Thus assume that . If there is a block with then playing the rule on this block decreases by . Otherwise, there must be at least one . Then, using Table 1, removing any decreases by since the blocks around have size or modulo .
If , then there is a move to a word with . Indeed, as before, there must be a block with . Then playing if or if on this block leads to a word with .
Finally, if , there is a move to a word with . We do the same reasoning than before to find a move from to . If there is a block of size or a next to a block of size , we remove the block of size or . If not, we remove any between two blocks of size .
We conclude with the proof by applying Lemma 2 with the partition given by , , , . ∎
Theorem 10.
The Grundy values of the game can be computed by a DFA.
Proof.
By Lemma 9, we just need to compute the value . This is done by the automaton depicted in Figure 3. There are 12 states. A state is denoted by where is the value and is the size modulo 3 of the last block of of . Reading from a state leads to state (values are taken modulo 4 for and modulo 3 for ). Reading from a state leads to state with if , if .
∎
What could happen if we just replace the rule by ? Surprisingly, we did not find an automaton for the game even though the Grundy values of this game seem to be bounded as suggested by computer experiments. For words of length at most 20, the Grundy function is bounded by . This leads to the following open question.
Question 11.
Are the Grundy values of the game bounded ? Are the corresponding sets regular ?
3.3 The game
We now prove that for the game , the corresponding sets are again regular and give a DFA that computes the Grundy values. As before, every word in can be written as
where and . We now write . For , let be the number of blocks of size modulo 4. Finally, we define for any word the triplet of .
For convenience reasons, we will denote the triplet by the word . As an example, the word has , , and thus . As before, the value is enough to compute the Grundy values.
Lemma 12.
Let , the Grundy value of in the game is determined by , i.e.,
Note that the values are paired with their complement
Proof.
We denote by , the potential candidates for , that are:

;

;

;

.
We aim to prove that . We first list the evolution of depending on the rule that is played.

The rule is played on a block . Table 2
gives the vector (in a compact form) that is applied to
in function of the values of and the rule . As an example, consider the case and the rule . One block of size is replaced by a block of size . Thus the vector applied to is (values are taken modulo 2)..0 1 2 3 1 001 100 110 011 2 010 101 010 101 3 100 110 011 001 Table 2: Variation of with the rules on a block . 
The rule is played. Let and be the two blocks around the that is removed. Table 3 gives the vector applied to depending on the values of and .
0  1  2  3  
0  100  100  100  100 
1  100  110  011  001 
2  100  011  100  011 
3  100  001  011  110 
In both cases, there is no variation with vector or which proves that all the sets are stable. We now prove that for any word in there is a move to a word in if .
First note that, except if contains only ’s and an even number of them, it is always possible to change by either vector or . Indeed, consider such a word . If there is a block of ’s of size or , then playing to any of this block changes the value of by or . Otherwise, there are only blocks of size or (modulo 4), and necessarily one . Then playing to any changes the value of by or (according to Table 3). This remark implies that there is always a move from a word in to and from a word in to .
Second, we prove that if belongs to , it is always possible to change by either vector or vector . By definition of and , there is always in either a block of size or a block of size modulo 4. Then, using Table 2, playing (in the first case) or (in the second case) changes the value of with vector (in the first case) or (in the second case). This implies that there is always a move from a word in to and from a word in to .
Third we prove that if belong to , it is always possible to change by either vector or vector . As before, must contain either a block of size or a block of size modulo 4. Then playing changes the value of with vector (in the first case) or (in the second case). This implies that there is always a move from a word in to and from a word in to .
Lemma 2 yields that for all . ∎
Theorem 13.
The Grundy values of the game can be computed by a DFA.
Proof.
We construct a DFA that computes the Grundy values of the game . By Lemma 12, one just needs to compute the value of , which, by definition of , can be done by an automaton that stores the value of , , modulo 2 and the number modulo 4 of in the last block. Actually, all this information is not needed if one just want the Grundy values. Indeed, storing only and the parity of the last block of is then enough. The main reason is that if changes with complement vectors when adding or if the parity of the last block of is the same, and thus the Grundy value remains the same. As an example, if ends with an odd number of and is read, then the vector applied to is if ends with one and if it ends with . The automaton computing the Grundy values in this way is depicted in Figure 4. It has eight states, a state is denoted by where is the Grundy value and the parity of the number of in the last block. As an example, from state , when reading , changes by vector or and thus the Grundy value that was is now and there are now an even number of . Hence the new state is . When reading , changes by vector and thus the Grundy value is now and the final letter is , thus the new state is .
∎
One could hope to show a similar result for each game of the form , by computing the number of and blocks of of size , , , …, modulo and finding some invariant for the Grundy values. However, this method already fails for since the word is a position for this game whereas is not. Note that we have computed the Grundy values for all words of length up to for this game and already found Grundy values:
This suggests that the automaton, if it exists for this game, is not as simple as it was for or .
4 Does a regular set of positions imply regular sets of Grundy values?
Given a rewrite game, deciding whether each set forms a regular language remains an open problem in a certain number of cases. Therefore, it seems natural to know whether a positive or a negative answer can be given without considering all the sets. A first step towards this direction has been given by Waldmann, who obtained the following result [9, Thm. 6].
Theorem 14 (Waldmann, 2002).
For all takingandbreaking games, if the language is regular, then the Grundy function is bounded, and all the Grundy languages are regular.
Hence in the case of takingandbreaking games, the regularity of implies the regularity of all the languages . In our different setting of takingandmerging games, Waldmann’s proof cannot be transposed easily. In addition, the situation does not seem that clear. Let us consider a particular game.
Theorem 15.
For the game , the set of positions is regular.
Proof.
Consider the partition of into two sets
The set satisfies the stability property of Lemma 2: take any word in and apply one of the reductions. The resulting word is such that
Hence there is no move between two words in .
The set is absorbing: take a word such that . If , then using the reduction leads to the set . Otherwise, contains only ’s. Notice that it contains at least two ’s and using the reduction leads again to the set . Now take a word such that . The argument is similar. If , then using the reduction leads to the set . Otherwise, contains only ’s. Notice that it contains at least two ’s and using the reduction leads again to the set .
Hence according to Lemma 2, the set is the set of the positions of the game and is exactly . It is a straightforward exercise to see that is a regular language recognized by a DFA with three states. ∎
In parallel with this result, we have computed the first few elements from the sets of for all words of length less than :
Our program that iteratively builds the DFA for the Grundy function did not found any reasonable candidate up to this length. Hence a natural question arises.
Question 16.
For the game , is there a set that is not regular ?
In addition, our program found that new Grundy values regularly appear when the length of the words grows. For example, there are words of length with a Grundy value of . This correlation between the regularity of and a finite number of Grundy values has already been established for some rewrite games. Indeed, in the game duotaire, as well as for takingandbreaking games (see Theorem 14), an argument to ensure that is not regular consists in showing that the Grundy values are not bounded. We wonder whether this property remains true for takingandmerging games:
Question 17.
Are there takingandmerging games for which the set is regular but the Grundy function is not bounded ?
Note that in Question 17, the converse property does not hold. Indeed, a game for which the Grundy values are bounded does not necessarily has a regular language for . Consider the example of the game detailed in Section 2.2, for which is proved to be not regular (and where the Grundy values do not exceed ).
5 Winning positions and regular languages
Here we consider slightly more general rewriting rules and show that a very simple problem then become undecidable. More precisely we consider strongly terminating rewriting games, as defined below.
Definition 18.
A rewriting game is called strongly terminating if every reduction is such that .
As the name suggests, a strongly terminating game is such that, from any given starting position, the game is terminating. For such a game, there is a trivial algorithm computing the Grundy value of a given position, although in the worst case, this algorithm runs in exponential time with respect to the length of the starting position. We consider here the following more general problem.
Problem 19.
Given a strongly terminating game , and a langage of “starting positions”, decide whether there is a position for belonging to .
The main result of this section is the following.
Theorem 20.
Problem 19 is undecidable, even though the language is a starfree regular language.
We will prove Theorem 20
by a reduction from the halting problem of a deterministic Turing machine on the empty word. It takes indeed the rest of Section 5.
5.1 Instanciation of Problem 19
In the following, we consider a deterministic Turing machine defined by

, the finite set of states;

, the initial state;

, the accept and reject state;

, the finite alphabet of tape symbols;

, the left marker of the tape;

, the blank symbol;

, the set of input symbols^{2}^{2}2Since we only consider the empty word as input, the set of input symbols is irrelevant.; and

, the partial transition function.
We denote by the set of halting states, that is: . As usual, we assume that the head of is on the symbol $ at the beginning of a computation. We also assume for every state in that , if it is defined, is always equal to for some state . For more details on Turing machine or the Halting Problem, see for instance [3, 7].
Now, let us define the instance of Problem 19 to which we reduce the halting of on the empty word.
In the following, the first player is called A(lice) and the second one is called B(ob).
First, the alphabet of the game is , where are defined above, where is the ‘erasable’ symbol that will make strongly terminating, and where
(1) 
is the set of ‘head symbols’, which indicate the position and direction of the head, as well as the current player (A or B).
Second, the reductions are defined by equations (2) to (11), below. For every state in , the leftshift reductions are as follows.
(2)  
(3) 
Symmetrically, the rightshift reductions are as follows, for every state in .
(4)  
(5) 
The righttransition reductions are as follows, for every states in and for every tape symbol in such that .
(6)  
(7) 
Similarly, if , the lefttransition reductions are as follows.
(8)  
(9) 
Finally, the halting reductions are as follows, for every states in and for every tape symbol in such that , for some , and .
(10)  
(11) 
Third,the language of starting positions is
(12) 
It may be verified that, thus defined, is indeed strongly terminating and is a starfree regular language.
5.2 Game is a zeroplayer game
First, easy inductions show the following.
Lemma 21.
Let us consider the game starting from a starting position . Let be a later position in a run of the game.

Position contains exactly one occurrence of a symbol from .

If it is player A’s turn, contains no occurrence of or , and contains exactly one occurrence of either or .

If it is player B’s turn, then contains no occurrence of or and contains at most one occurrence of a symbol in .
It follows immediately that the game is in fact asymmetrical. The only reduction that player B can ever apply are (3) and (5); while the only reduction that player A can ever apply are the other ones (i.e., rules (2), (4), (6), (7), (8), (9), (10) and (11)). Next lemma states the condition for the game to end.
Lemma 22.
Let us consider the game starting from a position in . If player A makes a halting move, then she wins the game. Otherwise, player B always has a move to make afterwards.
Proof.
Finally, let us show that is a zeroplayer game, i.e. each move of the game is forced.
Proposition 23.
Let us consider the game starting from a position in . There is a unique sequence of words and a unique sequence of reductions such that for every integer ,
Comments
There are no comments yet.