Question

Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful.

A LBA with stack should not be Turing complete, because its halting problem should be decidable. (It seems to be equivalent to the halting problem for a PDA).

Can a deterministic LBA with stack decide all problems decided by a nondeterministic LBA?

Or on the other hand, maybe a LBA with stack is (provably) not more powerful than a LBA?


Edit I think I found out how a deterministic LBA with stack can simulate a nondeterministic LBA. The stack can be used to store and recall the current state of the external memory (the linear bounded memory) as often as needed. The internal state is finite, so there is a global bound for the maximal number of nondeterministic moves available in a single step. So backtracking can be used to recursively simulate the result of each nondeterministic move.

I will have to think about how to make these two observations (halting problem is decidable, nondeterministic LBA can be simulated deterministically) more rigorous, before self-answering. I'm away next week, so don't hold your breath.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top