16
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.