Linear bounded automaton

The strong and the weaker definition lead to the same computational abilities of the respective automaton classes,[1]: 225  by the same argument used to prove the linear speedup theorem.

Linear bounded automata are acceptors for the class of context-sensitive languages.

[2] In 1963, Peter Landweber proved that the languages accepted by deterministic LBAs are context-sensitive.

Kuroda introduced the more general model of (nondeterministic) linear bounded automata, and adapted Landweber's proof to show that the languages accepted by nondeterministic linear bounded automata are precisely the context-sensitive languages.

This problem can be phrased succinctly in the language of computational complexity theory as: The second LBA problem is whether the class of languages accepted by LBA is closed under complement.