eCommons

 

The LBA Problem and its Importance in the Theory of Computing

Other Titles

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 L1, such that L1 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.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

1973-05

Publisher

Cornell University

Keywords

computer science; technical report

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-171

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record