<p><strong>With epsilon pushes</strong></p>

<p>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.</p>

<p>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.</p>

<p>We design $A$ such that a word is <em>not</em> accepted if and only it is of the form:</p>

<p>$$\#C_0\&amp;C_0\$(\overline{C_0})^R\#C_1\&amp;C_1\$(\overline{C_1})^R\#C_2\&amp;C_2\$(\overline{C_2})^R\dots\#C_n\&amp;C_n\$(\overline{C_n})^R$$
where</p>

<ol>
<li>Each $C_i$ encodes a valid configuration of $M$</li>
<li>$C_0$ is initial, $C_n$ is accepting</li>
<li>$u^R$ is the reverse of a word $u$</li>
<li>$\overline{u}$ is a copy of $u$ using pop letters</li>
<li>$\#,\&amp;,\$$ are special separation symbols not in the alphabet of $M$</li>
<li>$C_i\to C_{i+1}$ is always a valid transition of $M$</li>
</ol>

<p>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.</p>

<p><strong>Pushing words</strong></p>

<p>As for the variants where words are pushed, it seems that the determinizability proof in the <a href="http://madhu.cs.illinois.edu/stoc04.pdf" rel="nofollow noreferrer">original paper</a> 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.</p>

CC BY-SA 3.0
2017-11-29T15:42:10.633Z
2017-11-29T18:13:03.870Z
2017-11-29T18:13:03.870Z
Denis
<p>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.</p>

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

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

<p>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.</p>

<p>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 <a href="http://dl.acm.org/citation.cfm?id=1007390">this paper</a> for more.</p>

CC BY-SA 3.0
2013-07-19T15:00:49.523Z
it seems the obvious question is whether such automata are equivalent to standard pushdown automata with the "words" converted into sequences of states? afaik, yes? if not, an illustrative example of a case where it fails would be helpful.
vzn
CC BY-SA 3.0
2013-07-22T09:35:37.960Z
@vzn They cannot be equivalent. Those visibly PDAs seem to be strictly weaker. Last time I checked, CFLs were not closed under intersection.
Kai
CC BY-SA 3.0
2013-07-22T15:57:13.747Z
So, VPDAs are closed under intersection, and are known to be properly between $REG$ and $DCFL$. However, I have no idea if my variant is closed under intersection, so it could be equivalent. I doubt it is, but I'm unsure.
Joey Eremondi
CC BY-SA 3.0
2013-07-23T13:07:08.213Z
This paper http://dx.doi.org/10.1145/1516512.1516518 gives a grammar characterization of VPDAs, and a construction for converting between the grammars and VPDAs. Possibly the grammar can be used to simulate pushing entire words?
Evgenij Thorstensen
CC BY-SA 3.0
2013-07-23T14:08:20.490Z
Why would pushing a word on a symbol be equivalent to allowing pushes on eps-transitions?
domotorp
CC BY-SA 3.0
2013-07-23T15:55:15.677Z
It likely wouldn't be equivalent, but $\epsilon$-transitions would be at least as powerful as pushing words. To push a word onto the stack, you follow a number of $\epsilon$-transitions, each pushing an individual letter.
Joey Eremondi
CC BY-SA 3.0
2013-07-24T07:38:51.070Z
It seems that with an eps-transition push you can push anything, so just never push on letters, but instead move to a state that makes an eps-transition and push whatever you want to.
domotorp
CC BY-SA 3.0
2013-07-29T16:21:25.510Z
Anyone want to summarize the comments into an answer so I can award the bounty?
Joey Eremondi
<reference-request><fl.formal-languages><automata-theory><context-free><context-free-languages>
Are there variants of visibly pushdown automata that allow pushing of words onto the stack?
Joey Eremondi
# Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

(Asked by: username_0 on 2013-07-18)

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](http://dl.acm.org/citation.cfm?id=1007390) for more.

**Tags:** reference-request, fl.formal-languages, automata-theory, context-free, context-free-languages

> **Comments:**
> **username_1**: it seems the obvious question is whether such automata are equivalent to standard pushdown automata with the "words" converted into sequences of states? afaik, yes? if not, an illustrative example of a case where it fails would be helpful.  
> **username_2**: @username_1 They cannot be equivalent. Those visibly PDAs seem to be strictly weaker. Last time I checked, CFLs were not closed under intersection.  
> **username_0**: So, VPDAs are closed under intersection, and are known to be properly between $REG$ and $DCFL$. However, I have no idea if my variant is closed under intersection, so it could be equivalent. I doubt it is, but I'm unsure.  
> **username_3**: This paper http://dx.doi.org/10.1145/1516512.1516518 gives a grammar characterization of VPDAs, and a construction for converting between the grammars and VPDAs. Possibly the grammar can be used to simulate pushing entire words?  
> **username_4**: Why would pushing a word on a symbol be equivalent to allowing pushes on eps-transitions?  
> **username_0**: It likely wouldn't be equivalent, but $\epsilon$-transitions would be at least as powerful as pushing words. To push a word onto the stack, you follow a number of $\epsilon$-transitions, each pushing an individual letter.  
> **username_4**: It seems that with an eps-transition push you can push anything, so just never push on letters, but instead move to a state that makes an eps-transition and push whatever you want to.  
> **username_0**: Anyone want to summarize the comments into an answer so I can award the bounty?  

---

## 1 answers

### Answer by username_5 on 2017-11-29. Score: 3

**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](http://madhu.cs.illinois.edu/stoc04.pdf) 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.


---

