Linear Bound Automaton Power Please tell me is their deterministic linear bound automaton same power as non-deterministic linear bound automaton to recognize any language?
Your question is equivalent to asking whether or not $DSPACE(O(n)) = NSPACE(O(n))$, which is an open problem, known as the first LBA problem.