Show simple item record

dc.contributor.authorHartmanis, Jurisen_US
dc.contributor.authorBerman, L.en_US
dc.date.accessioned2007-04-23T17:49:14Z
dc.date.available2007-04-23T17:49:14Z
dc.date.issued1975-05en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-242en_US
dc.identifier.urihttps://hdl.handle.net/1813/6988
dc.description.abstractIn 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.en_US
dc.format.extent784360 bytes
dc.format.extent251587 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleA Note on Tape Bounds for SLA Language Processingen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics