Zigzag Game

Mikołaj Bojańczyk

zajęcia / courses

The Zigzag Theorem says that two languages $L,K \subseteq A^*$ can be separated by a piecewise testable language if and only if there is no infinite zigzag between them. Therefore, to prove that separability is decidable, it suffices to decide if there exist infinite zigzags. We begin by phrasing the problem in purely monoid terms.

Let $M$ be a finite monoid. Define a zigzag between $m,n \in M$ to be a zigzag over the alphabet $M$ , which alternates between words of type $m$ and type $n$ . The following fact is easy to see.

Fact. Let languages $L,K \subseteq A^*$ be recognised by a surjective monoid morphism $h : A^* \to M$ . Then there is a zigzag between $L$ and $K$ if and only if in the monoid $M$ there is a zigzag beteen $m,n$ for some $m \in h(L)$ and $n \in h(K)$ .

The zigzag game. By the above fact, deciding the existence of zigzags reduces to the question of deciding, for a given finite monoid, which pairs admits zigzags. To characterise this, we introduce a safety game, called the zigzag game of the monoid. The zigzag game is a special case of a safety game.

To highlight the character of the game, we call the two players Zigzag and Doubter, with player Zigzag playing the role of player $0$ in a safety game (i.e. the player who wins when the game lasts forever). The game has two kinds of positions. Positions owned by player Zigzag are pairs $(m,n) \in M^2$ , while positions owned by player Doubter are words over the alphabet

$\Gamma = \{(1,m,n),(m,m,m) : m,n \in M\}$

The intuitive idea is that $(1,m,n)$ represents a sequence that is growing in the Higman ordering, which begins with the empty word and then alternates between $m$ and $n$ , while $(m,m,m)$ represents a constant sequence which has the letter $m$ on all positions.

The game is played as follows. In a position of the form $(m,n)$ , player Zigzag chooses some word $w \in \Gamma^*$ such that the product of the word, in the monoid $M^3$ , is equal to $(m,n,m)$ . If there is no such word then player Zigzag loses immediately. In a position of the form $w \in \Gamma^*$ , player Doubter chooses some letter $(x,y,z)$ that appears in this word, and the game continues from position $(y,z)$ . If player Doubter cannot choose a letter, i.e. $w$ is empty, then player Doubter loses immediately.

If the game lasts forever, then player Zigzag wins (i.e. this is a safety game where player Zigzag is the $0$ player).

Theorem (Zigzag Game Theorem). In a finite monoid $M$ , there is a zigzag between $m$ and $n$ if and only if player Zigzag has a winning strategy from position $(m,n)$ .

Before proving the above theorem, we observe how it allows us to decide whether or not there exists a zigzag between $m$ and $n$ in the monoid. In principle, the game is infinite, because player Doubter has infinitely many positions. However, one can consider a reduced version of the game, which is equivalent, and has finitely many positions.

The reduced version of the zigzag game is defined as follows. The positions of player Zigzag are the same, i.e. they are pairs $(m,n)$ . The difference is in positions of player Doubter – these are now subsets of $\Gamma$ , of which there are finitely many. When in a position $(m,n)$ , instead of choosing a word in $\Gamma^*$ , player Zigzag chooses a subset $X \subseteq \Gamma^*$ such that there exists a word $w \in X^*$ which evaluates to $(m,n,m)$ . In other words, player Zigzag chooses some $X$ which generates in $(m,n,m)$ in the monoid $M^3$ . In a set $X$ , player Doubter simply chooses an element $(x,y,z) \in X$ and the game continues from position $(y,z)$ . It is easy to see that, when restricted to positions of the form $(m,n)$ , the two games are equivalent, i.e. player Doubter has a winning strategy in the zigzag game if and only if he has a winning strategy in the reduced zigzag game. Since the reduced zigzag game is a safety game with a finite arena, one can compute positions where player Zigzag has a winning strategy, and therefore, by equivalence of the two games and the Zigzag Game Theorem, one can decide which pairs $m,n$ in the monoid admit zigzags.

It remains to prove the Zigzag Game Theorem.

Proof. We only prove the more interesting left-to-right implication. We will prove that if there is a zigzag between $m$ and $n$ , then in position $(m,n)$ player Zigzag can choose some word $w \in \Gamma^*$ , such that for every letter $(x,y,z)$ used by that word, there is a Zigzag between $y$ and $z$ .

To prove the above claim, we introduce some notation. Define a growing sequence to be a sequence $g \in (M^*)^\omega$ which is growing with respect to the Higman ordering, but not necessarily strictly growing, i.e. consecutive elements can be equal. The set of growing sequences forms a monoid when equipped with pointwise concatenation:

$\overbrace{(w_1,w_2,\ldots)}^g \cdot \overbrace{(v_1,v_2,\ldots)}^h = \overbrace{(w_1v_1,w_2v_2,\ldots)}^{g \cdot h}$

Define the type of a growing sequence $g$ to be the sequence of types of the words in $g$ , i.e. the type is an element of $M^\omega$ . A zigzag between $m$ and $n$ is a growing sequence whose type is $m,n,m,n,\ldots$ . The left-to-right part of the theorem follows immediately from the following lemma.

Lemma. If there exists a zigzag between $m,n$ , then there exist a zigzag which can be decomposed as

$g_1 \cdots g_k$

where $g_1,\ldots,g_k$ are growing sequences such that each one of them has a type of the form

$x,x,x,\ldots \qquad \text{or} \qquad 1,x,y,x,y,x,y,\ldots$

for some $x,y \in M$ .

It remains to prove the lemma. Consider a zigzag between $m$ and $n$ . Here is a picture of such a zigzag, with the rows representing words in thezigzag, and columns representing the letters (the letter is black when it first appears, and in later rows it is grey):

Note that the picture has actually infinitely many columns, because each row introduces a new letter (and therefore the set of columns is some countable totally ordered set). Each block of consecutive columns represents a growing sequence. The first row in the zigzag has a finite number of letters, say $k$ . (In the above picture, $k=2$ .) Let us distinguish these letters as $k$ columns (i.e. constant growing sequences), pictured in red below:

The red columns are constant sequences, in particular growing sequences, and therefore each red column has a type of the form $x,x,x,\ldots$ as required in the lemma. Let us group the remaining columns, so that columns are in the same group if they are not separated by red columns, i.e. columns that correspond to letters from the first row. This is shown in the following picture, with the remaining columns grouped into blue groups:

Clearly there will be at most $k+1$ blue groups, and each one will be a growing sequence. Furthermore, each blue group begins with the empty word, i.e. its type begins with $1$ . Using the pigeon hole principle, we can remove rows so that the result is still a zigzag between $m$ and $n$ , but each of the blue groups has a type of the form $1,x,y,x,y,\ldots$ as required by the lemma. This completes the proof of the lemma and of the the theorem. $\Box$

zajęcia / courses

Zigzag Game

Leave a Reply