Theorem The following are equivalent.
- $L$ is accepted by a deterministic LBA with stack
- $L$ is accepted by a nondeterministic LBA with stack
- $L$ is in $\operatorname{DTIME}(c^n)$ for some constant $c$.
So the computational power of a LBA with stack for decision problems is well understood. The exponential runtime limits the usefulness of this knowledge in practice. But the notion of an LBA with stack can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of
- a read-only input tape, surrounded by endmarkers,
- a finite state control,
- a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
- a stack
In "Hopcroft/Ullman (1979) Introduction to Automata Theory, Languages, and Computation (1st ed.) we find:
Theorem 14.1 The following are equivalent for $S(n)\geq\log n$.
- $L$ is accepted by a deterministic $S(n)$-AuxPDA
- $L$ is accepted by a nondeterministic $S(n)$-AuxPDA
- $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.
with the surprising:
Corollary $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.
The proof consists of three parts: (1) If L is accepted by a nondeterministic $S(n)$-AuxPDA with $S(n)\geq \log n$, then $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$. (2) If $L$ is in $\operatorname{DTIME}(T(n))$, then $L$ is accepted in time $T^4(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input). (3) If $L$ is accepted in time $T(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input), then $L$ is accepted by a deterministic $\log T(n)$-AuxPDA.
Part (1) is basically a rigorous proof that the "halting problem is decidable", where the number of operations was counted thoroughly. Part (2) is the creative idea that prepares the stage for part (3). Part (3) uses the auxiliary storage for tracking the time step, which allows to reconstruct the head position due to the very simple forward-backward head scan pattern, and the stack for recursive backtracking. (So this proof also contains the two observations which I wanted to make more rigorous. This answer is already long enough anyway, so I won't go into more detail here.)
This leads to the following answer for the initial question Is a LBA with stack more powerful than a LBA without?: The question is equivalent to a well know open problem, and the expectation is that it is indeed more powerful.
