16

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.

Joey Eremondi
  • 2,832
  • 15
  • 29
  • 2
    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
  • 2
    @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 09: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. – Joey Eremondi Jul 22 '13 at 15:57
  • 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 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
  • 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 Jul 23 '13 at 15:55
  • 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 Jul 24 '13 at 07:38
  • Anyone want to summarize the comments into an answer so I can award the bounty? – Joey Eremondi Jul 29 '13 at 16:21

1 Answers1

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

Denis
  • 8,843
  • 28
  • 55