Skip to main content


eCommons@Cornell

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: May-1973
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-171
Abstract: In this paper we study the classic problem of determining whether the deterministic and non-deterministic context-sensitive languages are the same or, equivalently, whether the languages accepted by deterministic and non-deterministic 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 hardest-tape recognizable non-deterministic context-sensitive language $L_{1}$, such that $L_{1}$ is a deterministic context-sensitive language if and only if the deterministic and non-deterministic context-sensitive languages are the same. We show furthermore, that many decision problems about sets described by regular expressions are instances of these tape-hardest recognizable context-sensitive languages. Thus, it follows that non-determinism 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 non-deterministic linearly bounded automaton if and only if the family of context-sensitive languages is closed under complementation.
URI: http://hdl.handle.net/1813/6015
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
73-171.pdf2.76 MBAdobe PDFView/Open
73-171.ps829.38 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us