Linear-Bounded Automaton (LBA) a nondeterministic Turing machine whose tape is bounded by a constant times the length of the input