## 2-VPAs are not determinizable

### - by S. La Torre, P. Madhusudan, and G. Parlato

Here is a proof showing that 2-VPAs (or 2-OVPAs)

are not determinizable. This proves that Theorem 6 of the paper

2-Visibly Pushdown Automata (by Dario Carotenuto, Aniello Murano

and Adriano Peron) is wrong.

The proof is a simple adaptation of the non determinizability proof for

bouded-phase visibly pushdown automata over multiple stacks given in

A Robust Class of Context-Sensitive Languages (by Salvatore La Torre,

P.Madhusudan, and Gennaro Parlato).

We prove that there is a simple language that cannot be accepted by any

2-VPA (or 2-OVPA).

Let a and b correspond to pushes of the first stack only and second stack

only respectively. Let c and d correspond to pops of the first stack while

x and y correspond to pops of the second. The language is

L = { (ab)^{ i}. c^{ j}.d^{ {i-j}}. x^{ j}.y^{ {i-j}} | i &isin N, j <= i }

In other words, we want to check if the number of pops "c" is equal to

the number of pops "x".

First, L is accepted by a nondet 2-stack VPA.

The VPA can, on a and b, push # onto both stacks, and nondeterministically

switch to a mode where it pushes $ onto both stacks. Intuitively this

switch corresponds to the guess of what j is. On popping, it checks that

c's get popped on $ and d's on #, and y's on $ and x's on #.

Next, L is not determinizable: Assume the contrary and let A be a deterministic

VPA accepting L. After reading (ab)^i c^j d^{i-j}, the first stack must

be empty, and the second stack is *independent* of j (i.e. the automaton

must reach the same content of the second stack on (ab)^{ i} c^{ j'} d^{ {i-j'}}

for any j', since the pushes on the stack were done before discovering j

and A is deterministic. By choosing i large enough, larger than the number

of control states in A, it is easy to see that there is some j and j'

(j and j' different and less than i), such that A reaches the same configuration

(state+stacks) on (ab)^{ i} c^{ j} d^{ {i-j}} and (ab)^{ i} c^{ j'} d^{ {i-j'}}.

Hence appending the word x^{ j}.y^{ {i-j}} must be either accepted after

both the above words or rejected after both the above words, both contradicting

the assumption that A accepts L.