6
$\begingroup$

It is known that a PDA with two stacks is equivalent to a TM.

On the other hand a PDA with one stack is capable to recognise only context-free languages.

Hence there is a kind of a gap between the class of PDA with one stack and the class of PDA with two stacks which should be capable to recognise only context-sensitive languages.

I feel like it should be already an examined question, but I couldn't find an answer: what restrictions should we apply to a PDA with two stacks in order to make it equivalent to a Linear-bounded automaton?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ A linear bound on the max size of one of the two stacks. $\endgroup$
    – Vor
    Jul 21, 2019 at 19:23
  • 1
    $\begingroup$ @Vor's answer is quite good. If a language can be decided by an LBA, then we can simulate this LBA with a two stack pushdown automaton where one stack's height is linearly bounded. However, the other direction looks a little bit tricky. Any ideas of how to show it? $\endgroup$
    – Michael Wehar
    Jul 21, 2019 at 20:25
  • 1
    $\begingroup$ Thanks lads for you help a lot! This gives me some sort of ideas. However ideally I would also love to know if this particular small problem has been already examined and there are maybe some papers about it. $\endgroup$
    – Andrey Lebedev
    Jul 21, 2019 at 20:56
  • 1
    $\begingroup$ There are many different extensions and variants of PDA's. For example, (1) adding multiple stacks with various notions of bounded switching between the stacks (phase switching, context-switching, order restriction). (2) Adding alternation between universal & existential states. (3) Stack automata which allow reading below the top of the stack. (4) Auxiliary PDA's which allow a bounded auxiliary work tape. (5) Adding bounded height counters or bounded height stacks. (6) Allowing input tape to be two-way with bounded or unbounded number of turns. (7) Multi-head PDA's. $\endgroup$
    – Michael Wehar
    Jul 21, 2019 at 21:28
  • 1
    $\begingroup$ A lot is known about what complexity classes are captured by the different variants of pushdown automata. For example, I think that alternating O(n)-time bounded pushdown automata with two stacks is equivalent to LBA under polytime reductions. $\endgroup$
    – Michael Wehar
    Jul 21, 2019 at 21:29

1 Answer 1

Reset to default
6
$\begingroup$

A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA.

What happens if only one of the two stacks is linear bounded and the other is unlimited? I optimistically wrote a quick comment that the LBA equivalence holds also in this case ... but ...

It's easy to see/prove that a 2-stack PDA with a linear bound only on one stack can simulate a LBA with one stack; and it is an open problem if a LBA with one stack is more powerful than a standard LBA.

For further details see T.Klimpel's answer to the question Is a LBA with stack more powerful than a LBA without?

This is a sketch of the proof that a PDA + 1 linear bounded stack + 1 unbounded stack (PDA+1B+1U) can simulate a LBA + 1 unbounded stack (LBA+1U)

Given a LBA+1U build a PDA+1B+1U in which the bounded stack is used to store the leftmost tape portion (reversed) and the unbounded stack stores the rightmost portion plus the unbounded content of the LBA stack.

A particular configuration of the LBA+1U:

    # x a y # stack: [b w   ]
        ^head

(where $\#$ are the endmarkers of the linear space, the head is on symbol $a$, the content of the tape is $xay$, the stack contains $bw$, $b$ is the top)

is represented into the PDA in this way:

    stack 1: [ > a x^R #  ]  (bounded stack)
    stack 2: [ y # b w       ]  (unbounded stack)

(where $>$ is a marker for the head position, $x^R$ is the reverso of $x$.

Suppose the LBA pops the b, change $a$ into $c$, moves left and pushes $d$ into the unbounded stack reaching this configuration:

    # x c y # stack: [ d w   ]
      ^head

The PDA can simulate that behavior in this way: it checks and pops the content of the unbounded stack using stack 1 as temporary storage:

    stack 1: [# y^R >a x^R # ]  (bounded stack)
    stack 2: [b w    ]  (unbounded stack)

Then it goes back to the head marker (storing "b" in its internal state)

    stack 1: [>a x^R # ]  (bounded stack)
    stack 2: [y # w    ]  (unbounded stack)

Then it moves left (and push c in the second stack simulating the a->c write operation):

    stack 1: [>x^R # ]  (bounded stack)
    stack 2: [c y # w    ]  (unbounded stack)

"goes" to the stack marker and push d:

    stack 1: [# y^R c >x^R # ]  (bounded stack)
    stack 2: [d w    ]  (unbounded stack)

then "goes back" to the head position:

    stack 1: [>x^R # ]  (bounded stack)
    stack 2: [c y # d w    ]  (unbounded stack)

Addendum

The proof that a PDA+2bounded stacks (PDA+2B) can simulate a LBA is similar.

For the other direction (a LBA can simulate a PDA+2B) the idea is to use two symbols to mark the top of both stacks $b_1, b_2$, and use the linear space to store the two bounded stacks "overlapped" (just use an expanded $\Sigma \times \Gamma \times \Gamma \times \{ b, b_1, b_2 \}$ alphabet).

By further expanding the alphabet you can store in the same (linear) space the original input, the head position of the PDA+2B, and an enumeration of the nodeterministic choices (there are at most $c|x|$ of them, one for each symbol of the initial input. Where $c$ depends only on the size of the transition table).

Then you can scan all the nondeterministic choices and simulate the behaviour of the PDA+2B using the top stack markers.

Note that if you allow epsilon transitions you must run two enumerations in parallel in order to check if the PDA+2B enters the same configuration due to $\epsilon$ transitions (i.e. detect if it loops forever)

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks for your answer. Though I am a bit surprised there are no (or I just couldn't find?) papers with this simple proof. Honestly, I have a doubt about if this condition about liner bounds is strict enough to make such a PDA strongly equivalent to LBA. Say shouldn't both stacks have a linear dependency on each other? $\endgroup$
    – Andrey Lebedev
    Jul 29, 2019 at 12:20
  • $\begingroup$ @AndreyLebedev: as I said the equivalence is easy to prove if both stacks have a linear bound. If only one have a linear bound and the other is unbounded , then it is an open problem if it is equivalent to a LBA (it's only easy to prove that it is equivalent to a LBA with a stack, and it is an open problem if a LBA with a stack is equivalent to a LBA). $\endgroup$
    – Vor
    Jul 29, 2019 at 13:14
  • $\begingroup$ Though I have upvoted your answer, having at least a sketch of this easy proof would be a great reason to accept your answer. Because, yes, it seems to be quite a natural requirement these liner boundaries, but I am pretty sure there are tricky peculiarities with this proof which may make it quite uneasy. $\endgroup$
    – Andrey Lebedev
    Jul 29, 2019 at 13:30
  • $\begingroup$ @AndreyLebedev: OK are you referring to the proof "PDA+2 linear bounded stacks = LBA" or the proof "PDA+1 unlimited stack+1 linear bounded stack = LBA+1 unlimited stack"? $\endgroup$
    – Vor
    Jul 29, 2019 at 14:58
  • 1
    $\begingroup$ A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA. This makes sense to me. :) $\endgroup$
    – Michael Wehar
    Jul 30, 2019 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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