A pumping lemma for automata with atoms

This is a straightforward generalization of the classical Pumping Lemma for regular languages. It was proved independently by the Warsaw team and by Filippo Bonchi, Daniela Petrisan and Alexandra Silva.

For a definition of an automaton with atoms, see our paper Automata theory in nominal sets.

Lemma. For any language $L\subseteq\mathbb{A}^*$ recognizable by an equivariant nondeterministic automaton with atoms, there exists a number $k\in\mathbb{N}$ such that for every word $w\in L$ of length at least $k$ there exist:

a decomposition $w=xyz$ , and
an atom bijection $\pi:\mathbb{A}\to\mathbb{A}$ ,

such that

$|y|\geq 1$ ,
$|xy|\leq k$ ,
for every $n\in\mathbb{N}$ , the word
$x y (y\cdot \pi)(y\cdot \pi^2)(y\cdot \pi^3)\cdots(y\cdot \pi^n)(z\cdot \pi^n)$

is in $L$ .

Proof. The argument is completely analogous to the classical case. Let $A$ be a nondeterministic automaton that recognizing $L$ , and let $k$ be the number of orbits of states in $A$ . For a fixed $w\in L$ with $|w|\geq k$ , take any accepting run of $A$ on $w$ . After some $l\leq k$ steps, the run visits a state $q_l$ which shares the orbit with some state visited before (say, after $m<l$ steps, and denote the state $q_m$ ). Decompose

$w=xyz$

so that $|x|=m$ and $|xy|=l$ .

Pick an atom bijection $\pi$ so that $q_m\cdot\pi=q_l$ ; it exists since $q_l$ and $q_m$ are in the same orbit of states. Since $A$ on the word $y$ can move from the state $q_m$ to the state $q_l$ , by equivariance, on the word $y\cdot\pi$ it can move from $q_l$ to $q_l\cdot\pi$ . By induction, on the word

$y(y\cdot \pi)(y\cdot \pi^2)(y\cdot \pi^3)\cdots(y\cdot \pi^n)$

$A$ can move from $q_m$ to $q_l\cdot\pi^n$ . Again by equivariance, $A$ on $z$ can move from $q_l\cdot\pi^n$ to an accepting state, since it can move to an accepting state from $q_l$ .

In this way we have constructed an accepting run of $A$ on

$x y (y\cdot \pi)(y\cdot \pi^2)(y\cdot \pi^3)\cdots(y\cdot \pi^n)(z\cdot \pi^n).$

Remark 1. The lemma works for any alphabet and any kind of atoms, or even for a straightforward generalization of automata to arbitrary $G$ -sets for a group $G$ , without any assumptions regarding finite supports.

Remark 2. The lemma is not particularly strong. For example, over the alphabet of equality atoms, the language of words where every letter appears at most once:

$L = \{a_1a_2\cdots a_n\mid a_i\neq a_j \mbox{ for } i\neq j\}$

satisfies the lemma, but is not recognized by a nondeterministic automaton. A few basic questions arise:

Does the lemma work for alternating automata?
Is there an easy pumping lemma for nondeterministic automata that would exclude $L$ above?
Is there an easy pumping lemma that would hold for deterministic automata and exclude standard examples of nondeterministic automata that do not determinize?

Edit 1 [April 5, 2014]: The answer to Question 1 above is negative. A counterexample is the language of those words of even length, where

all atoms in the first half are equal, and
all atoms in the second half are distinct.

This looks a bit like the $a^nb^n$ language, but is actually recognizable by an alternating automaton with atoms. (This was shown by Tomasz Wysocki in his MSc thesis, unfortunately written in Polish.) Clearly, our pumping pemma fails for this language.

Atompress

A pumping lemma for automata with atoms

Leave a Reply Cancel reply

Computation with atoms