<p>The 1998 chapter about the second LBA Problem, from <a href="http://link.springer.com/chapter/10.1007/978-3-642-60322-8_5#page-1" rel="nofollow noreferrer">Schöning and Pruim Gems of TCS</a> mentions the first LBA problem.
The chapter does not say much more than the <a href="http://en.wikipedia.org/wiki/Linear_bounded_automaton" rel="nofollow noreferrer">wikipedia article</a> though, apart from mentioning the related Savitch's theorem, whose optimality is a notorious <a href="https://cstheory.stackexchange.com/questions/2426/tight-lower-bounds-on-savitchs-theorem">open question</a>.</p>

<p>Perhaps by looking at papers quoting the Kuroda or Savitch paper you could get a picture of recent results in the field?</p>

CC BY-SA 3.0
2014-02-10T14:49:45.810Z
2014-02-10T14:49:45.810Z
2017-04-13T12:32:28.080Z
Joseph Stack
<p>Where I can find reference and documents on the work made for proving whether DLBA are equal NLBA nr not?
What is the underlying problem? Why it is still an open question in TCS? </p>

<automata-theory>
On equivalence of NLBA and DLBA
asdf
# On equivalence of NLBA and DLBA

(Asked by: username_0 on 2014-02-10)

Where I can find reference and documents on the work made for proving whether DLBA are equal NLBA nr not?
What is the underlying problem? Why it is still an open question in TCS?

**Tags:** automata-theory


---

## 1 answers

### Answer by username_1 on 2014-02-10. Score: 3 | Accepted answer

The 1998 chapter about the second LBA Problem, from [Schöning and Pruim Gems of TCS](http://link.springer.com/chapter/10.1007/978-3-642-60322-8_5#page-1) mentions the first LBA problem.
The chapter does not say much more than the [wikipedia article](http://en.wikipedia.org/wiki/Linear_bounded_automaton) though, apart from mentioning the related Savitch's theorem, whose optimality is a notorious [open question](https://cstheory.stackexchange.com/questions/2426/tight-lower-bounds-on-savitchs-theorem).

Perhaps by looking at papers quoting the Kuroda or Savitch paper you could get a picture of recent results in the field?


---

