Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

Question

I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack.

Alternately, a construction which allowed for symbols to be pushed on $\epsilon$-transitions could achieve the same goal.

Obviously, such variations can be formed, but I'm wondering if it ruins the closure and decidability properties that make VPAs interesting.

I'm looking at a construction where use the stack as a counter, incrementing it by constants based on the initial symbols read, then counting down based on other symbols read.

For anyone who doesn't know, visibly pushdown automata are ones where the alphabet can be divided into pushing symbols, popping symbols, and symbols not affecting the stack at all. The choice of pushing versus popping is entirely determined by the current symbol being read. They're closed under intersection, union, concatenation, star and complement, giving them a wealth of decidable properties. See this paper for more.

Answer 1

With epsilon pushes

For the version with pushes on epsilon-transitions, the undecidability proof of universality of pushdown-automata can be adapted to this new setting, so we lose at least the following properties: closure under complementation, determinizability, decidability of universality and inclusion.

Proof scheme: Take a Turing Machine $M$, we want to build a VPA $A$ with epsilon-pushes such that it is universal if and only if M has no accepting run.

We design $A$ such that a word is not accepted if and only it is of the form:

$$\#C_0\&C_0\$(\overline{C_0})^R\#C_1\&C_1\$(\overline{C_1})^R\#C_2\&C_2\$(\overline{C_2})^R\dots\#C_n\&C_n\$(\overline{C_n})^R$$ where

1. Each $C_i$ encodes a valid configuration of $M$
2. $C_0$ is initial, $C_n$ is accepting
3. $u^R$ is the reverse of a word $u$
4. $\overline{u}$ is a copy of $u$ using pop letters
5. $\#,\&,\$$ are special separation symbols not in the alphabet of $M$
6. $C_i\to C_{i+1}$ is always a valid transition of $M$

The VPA $A$ is forced to do pop on factors of the form $C_i^R$. $A$ can non deterministically guess a violation of either property, and verify it. The key is that it can either push on $C_i$, or do nothing, which allows to verify all conditions (actually guess their violations). In particular, it can guess that the first (or second) occurence of $C_i$ does not match $(\overline{C_i})^R$, by ignoring the other component. It can also guess that $C_i\to C_{i+1}$ is not a valid transition, by pushing both occurences of $C_i$, then popping one, push no $C_{i+1}$, and compare $(\overline{C_{i+1}})^R$ to the stack content. For other $C_j$ that are not part of the guessing, one component is pushed and the $(\overline{C_j})^R$ is popped.

Pushing words

As for the variants where words are pushed, it seems that the determinizability proof in the original paper on VPAs can be adapted to this setting. It suffices to adapt the construction so that stack symbols are of the form $(S,R,u)$ where $u\in A^*$ is a prefix of a word that can be pushed according to the transition function. When popping a letter $a$, $(S,R,va)$ is turned to $(S',R',v)$, where $S'$ and $R'$ are updated normally to reflect the current powerset construction status. However, this time we a priori get a deterministic pushdown automaton that is not visibly pushdown. At least this means that equivalence and universality are decidable.