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/6988
Title: A Note on Tape Bounds for SLA Language Processing
Authors: Hartmanis, Juris
Berman, L.
Keywords: computer science
technical report
Issue Date: May-1975
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-242
Abstract: In this note we show that the tape bounded complexity classes of languages over single letter alphabets are closed under complementation. We then use this result to show that there exists an infinite hierarchy of tape bounded complexity classes of sla languages between log n and log log n tape bounds. We also show that every infinite sla language recognizable on less than log n tape has infinitely many different regular subsets, and, therefore, the set of primes in unary notation, P, requires exactly log n tape for its recognition and every infinite subset of P requires at least log n tape.
URI: http://hdl.handle.net/1813/6988
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
75-242.pdf765.98 kBAdobe PDFView/Open
75-242.ps245.69 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us