In computer science, a linear bounded automaton (abbreviated LBA) is a restricted form of Turing machine that functions as a more accurate model of a real-world computer, as its definition does not assume an unlimited tape.

Formally, it satisfies the following three conditions:

  • Its input alphabet includes two special symbols, serving as left and right endmarkers.
  • Its transitions may not print other symbols over the endmarkers.
  • Its transitions may neither move to the left of the left endmarker nor to the right of the right endmarker.

In other words:

instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers.

An alternative, less restrictive definition is as follows:

  • Like a Turing machine, an LBA possesses a tape made up of cells that can contain symbols from a finite alphabet, a head that can read from or write to one cell on the tape at a time and can be moved, and a finite number of states.
  • An LBA differs from a Turing machine in that while the tape is initially considered to have unbounded length, only a finite contiguous portion of the tape, whose length is a linear function of the length of the initial input, can be accessed by the read/write head; hence the name linear bounded automaton. In 1963, Peter Landweber proved that the languages accepted by deterministic LBAs are context-sensitive. In 1964, S.-Y. 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.

LBA problems

In his seminal paper, Kuroda also stated two research challenges, which subsequently became famously known as the "LBA problems": The first LBA problem is whether the class of languages accepted by LBA is equal to the class of languages accepted by deterministic LBA. This problem can be phrased succinctly in the language of computational complexity theory as:

:First LBA problem: Is NSPACE(O(n)) = DSPACE(O(n))?

The second LBA problem is whether the class of languages accepted by LBA is closed under complement.

:Second LBA problem: Is NSPACE(O(n)) = co-NSPACE(O(n))?

As observed already by Kuroda, a negative answer to the second LBA problem would imply a negative answer to the first problem. But the second LBA problem has an affirmative answer, which is implied by the Immerman–Szelepcsényi theorem proved 20 years after the problem was raised. As of today, the first LBA problem still remains open. Savitch's theorem provides an initial insight, that NSPACE(O(n)) ⊆ DSPACE(O(n<sup>2</sup>)).

References