<p>We will give a winning strategy for Delilah. Let Samson choose his $c$ and $m$. Then Delilah chooses $w = a^n b^n$ for a large $n$ to be determined later. Let Samson choose his subsets $C^w_1,\ldots,C^w_c$ which we view as a coloring of the positions of $w$ with $2^c$ colors. Let $w'$ denote this colored word. The goal of Delilah at this point is to find a segment $w'[i,\ldots,j]$ of $w'$ with the following properties for an $r$ and a $t$ to be chosen later:</p>

<ol>
<li>$0 \leq i \leq j \leq n$ (thus the segment belongs to the first part of $w'$),</li>
<li>the $r$-neighborhoods (neighborhoods of radius $r$) of $i$ and $j$ in $w'$ are isomorphic,</li>
<li>for every $k \in [i,\ldots,j]$, the $r$-neighborhood of $k$ in $w'$ appears as $r$-neighborhood of at least $t$ other positions of $w'$.</li>
</ol>

<p>If she manages to do that, then she will choose her colored word to be
$$
v' = w'[0,\ldots,i-1] w'[i,\ldots,j]^2 w'[j+1,\ldots,2n-1].
$$ 
If $v$ is the ${a,b}$-word underlying $v'$, it will follow that $v$ does not belong to $L$ (because we pumped a non-empty segment of $a$'s), and Delilah has a winning strategy in the $m$-turn EF game on $w'$ and $v'$ (this follows from Hanf's Theorem if $r$ and $t$ are sufficiently large with respect to $c$ and $m$; see Theorem 1.4.1 in Ebinghaus and Flum book "Finite Model Theory").</p>

<p>Thus, it remains to show that if $n$ is sufficiently large with respect to $c$, $m$, $r$ and $t$ we can find a segment $w'[i,\ldots,j]$ as above. But this follows from a standard pigeonhole argument using the fact that the number of ismorphism types of $r$-neighborhoods is finite.</p>

<p>This worked for successor structures. With a linear order it will be a bit harder but I didn't think much about it.</p>

<p>Note that, not surprisingly, this argument looks a bit like "pumping" argument in automata. However, it is not as silly as just translating the formula to an automaton. I think it counts as a model-theoretic argument.</p>

CC BY-SA 2.5
2010-09-27T18:44:44.173Z
Doesn't my answer convince you?
slimton
CC BY-SA 2.5
2010-10-04T14:56:13.597Z
Oops, sorry, of course it does.  Though I'd be really interested to see what that would be with a linear order (and thus without Hanf's locality).  Thank you for that answer!
Michaël Cadilhac
CC BY-SA 2.5
2010-09-21T09:05:34.673Z
2010-09-21T09:05:34.673Z
slimton
<p>Immerman (Descriptive Complexity, 1999) presents the EF games for existential monadic second order (Ajtai-Fagin games) on page 127.  As $\exists$MSO on words is equivalent to regular languages, the game can be written as follows.</p>

<p>A language $L \subseteq \{a, b\}^*$ is regular if and only if Delilah has no winning strategy in the following game:<br/>
1. Samson chooses $c, m \in \mathbb{N}$,<br/>
2. Delilah chooses $w \in L$,<br/>
3. Samson chooses $c$ subsets $C_1^w, \ldots, C_c^w$ of the set of positions in $w$ (i.e. $\{0, \ldots, |w|-1\}$),<br/>
4. Delilah chosses $v \not\in L$ and $c$ subsets $C_1^v, \ldots, C_c^v$ of the set of positions in $v$,<br/>
5. Samson and Delilah play the $m$-turn EF game on $(\mathfrak{S}(w), C_1^w, \ldots, C_c^w)$ and $(\mathfrak{S}(v), C_1^v, \ldots, C_c^v)$,<br/>
where $\mathfrak{S}(w)$ is the structure associated with the word $w$, i.e. :
$$\mathfrak{S}(w) = \langle \{0, \ldots, |w|-1\}, SUCC, Q_a, Q_b \rangle$$
with $Q_l = \{p \;|\; w_p = l\}$, and $SUCC$ is the binary successor predicate.</p>

<p>I have two questions:<br/>
- How does one show that $\{a^nb^n \;|\; n \in \mathbb{N}\}$ is not regular, using an EF argument like this,<br/>
- Is it easier/harder to play those games (to show non-regularity) when one has an ordering rather than the successor relation? (Those are equivalent in existential MSO).</p>

<lo.logic><automata-theory><descriptive-complexity>
Ehrenfeucht-Fraïssé games (Ajtai-Fagin in fact) for regular languages.
Michaël Cadilhac
# Ehrenfeucht-Fraïssé games (Ajtai-Fagin in fact) for regular languages.

(Asked by: username_0 on 2010-09-20)

Immerman (Descriptive Complexity, 1999) presents the EF games for existential monadic second order (Ajtai-Fagin games) on page 127. As $\exists$MSO on words is equivalent to regular languages, the game can be written as follows.

A language $L \subseteq \{a, b\}^\*$ is regular if and only if Delilah has no winning strategy in the following game:  
1. Samson chooses $c, m \in \mathbb{N}$,  
2. Delilah chooses $w \in L$,  
3. Samson chooses $c$ subsets $C\_1^w, \ldots, C\_c^w$ of the set of positions in $w$ (i.e. $\{0, \ldots, |w|-1\}$),  
4. Delilah chosses $v \not\in L$ and $c$ subsets $C\_1^v, \ldots, C\_c^v$ of the set of positions in $v$,  
5. Samson and Delilah play the $m$-turn EF game on $(\mathfrak{S}(w), C\_1^w, \ldots, C\_c^w)$ and $(\mathfrak{S}(v), C\_1^v, \ldots, C\_c^v)$,  
where $\mathfrak{S}(w)$ is the structure associated with the word $w$, i.e. :
$$\mathfrak{S}(w) = \langle \{0, \ldots, |w|-1\}, SUCC, Q\_a, Q\_b \rangle$$
with $Q\_l = \{p \;|\; w\_p = l\}$, and $SUCC$ is the binary successor predicate.

I have two questions:  
- How does one show that $\{a^nb^n \;|\; n \in \mathbb{N}\}$ is not regular, using an EF argument like this,  
- Is it easier/harder to play those games (to show non-regularity) when one has an ordering rather than the successor relation? (Those are equivalent in existential MSO).

**Tags:** lo.logic, automata-theory, descriptive-complexity


---

## 1 answers

### Answer by username_1 on 2010-09-21. Score: 9 | Accepted answer

We will give a winning strategy for Delilah. Let Samson choose his $c$ and $m$. Then Delilah chooses $w = a^n b^n$ for a large $n$ to be determined later. Let Samson choose his subsets $C^w\_1,\ldots,C^w\_c$ which we view as a coloring of the positions of $w$ with $2^c$ colors. Let $w'$ denote this colored word. The goal of Delilah at this point is to find a segment $w'[i,\ldots,j]$ of $w'$ with the following properties for an $r$ and a $t$ to be chosen later:

1. $0 \leq i \leq j \leq n$ (thus the segment belongs to the first part of $w'$),
2. the $r$-neighborhoods (neighborhoods of radius $r$) of $i$ and $j$ in $w'$ are isomorphic,
3. for every $k \in [i,\ldots,j]$, the $r$-neighborhood of $k$ in $w'$ appears as $r$-neighborhood of at least $t$ other positions of $w'$.

If she manages to do that, then she will choose her colored word to be
$$
v' = w'[0,\ldots,i-1] w'[i,\ldots,j]^2 w'[j+1,\ldots,2n-1].
$$
If $v$ is the ${a,b}$-word underlying $v'$, it will follow that $v$ does not belong to $L$ (because we pumped a non-empty segment of $a$'s), and Delilah has a winning strategy in the $m$-turn EF game on $w'$ and $v'$ (this follows from Hanf's Theorem if $r$ and $t$ are sufficiently large with respect to $c$ and $m$; see Theorem 1.4.1 in Ebinghaus and Flum book "Finite Model Theory").

Thus, it remains to show that if $n$ is sufficiently large with respect to $c$, $m$, $r$ and $t$ we can find a segment $w'[i,\ldots,j]$ as above. But this follows from a standard pigeonhole argument using the fact that the number of ismorphism types of $r$-neighborhoods is finite.

This worked for successor structures. With a linear order it will be a bit harder but I didn't think much about it.

Note that, not surprisingly, this argument looks a bit like "pumping" argument in automata. However, it is not as silly as just translating the formula to an automaton. I think it counts as a model-theoretic argument.

> **Comments:**
> **username_1**: Doesn't my answer convince you?  
> **username_0**: Oops, sorry, of course it does.  Though I'd be really interested to see what that would be with a linear order (and thus without Hanf's locality).  Thank you for that answer!  

---

