A Note on Tape Bounds for SLA Language Processing
| dc.contributor.author | Hartmanis, Juris | en_US |
| dc.contributor.author | Berman, L. | en_US |
| dc.date.accessioned | 2007-04-23T17:49:14Z | |
| dc.date.available | 2007-04-23T17:49:14Z | |
| dc.date.issued | 1975-05 | en_US |
| dc.description.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. | en_US |
| dc.format.extent | 784360 bytes | |
| dc.format.extent | 251587 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-242 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6988 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | A Note on Tape Bounds for SLA Language Processing | en_US |
| dc.type | technical report | en_US |