# A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

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?

• A linear bound on the max size of one of the two stacks. – Vor Jul 21 '19 at 19:23
• @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? – Michael Wehar Jul 21 '19 at 20:25
• 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. – Andrey Lebedev Jul 21 '19 at 20:56
• 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. – Michael Wehar Jul 21 '19 at 21:28
• 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. – Michael Wehar Jul 21 '19 at 21:29

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   ]


(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   ]


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)


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)

• 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? – Andrey Lebedev Jul 29 '19 at 12:20
• @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). – Vor Jul 29 '19 at 13:14
• 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. – Andrey Lebedev Jul 29 '19 at 13:30
• @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"? – Vor Jul 29 '19 at 14:58
• A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA. This makes sense to me. :) – Michael Wehar Jul 30 '19 at 19:28