Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 Jul 19 '13 at 15:00
@vzn They cannot be equivalent. Those visibly PDAs seem to be strictly weaker. Last time I checked, CFLs were not closed under intersection. – Kai Jul 22 '13 at 9:35
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. – jmite Jul 22 '13 at 15:57
This paper 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 Jul 23 '13 at 13:07
Why would pushing a word on a symbol be equivalent to allowing pushes on eps-transitions? – domotorp Jul 23 '13 at 14:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.