eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/6015
Title:  The LBA Problem and its Importance in the Theory of Computing 
Authors:  Hartmanis, Juris Hunt, Harry B., III 
Keywords:  computer science technical report 
Issue Date:  May1973 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73171 
Abstract:  In this paper we study the classic problem of determining whether the deterministic and nondeterministic contextsensitive languages are the same or, equivalently, whether the languages accepted by deterministic and nondeterministic linearly bounded automata are the same. We show that this problem is equivalent to several other natural problems in the theory of computing and that the techniques used on the LDA problem have several other applications in complexity theory. For example, we show that there exists a hardesttape recognizable nondeterministic contextsensitive language $L_{1}$, such that $L_{1}$ is a deterministic contextsensitive language if and only if the deterministic and nondeterministic contextsensitive languages are the same. We show furthermore, that many decision problems about sets described by regular expressions are instances of these tapehardest recognizable contextsensitive languages. Thus, it follows that nondeterminism in Turing machine computations (using at least linear tape) can not save memory over deterministic Turing machine computations if and only if the equivalence of regular expressions can be decided by a deterministic linearly bounded automaton. It also follows that the equivalence of regular expressions can be decided by a nondeterministic linearly bounded automaton if and only if the family of contextsensitive languages is closed under complementation. 
URI:  http://hdl.handle.net/1813/6015 
Appears in Collections:  Computer Science Technical Reports Hartmanis, Juris

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
