Show simple item record

dc.contributor.authorHartmanis, Jurisen_US
dc.contributor.authorMahaney, Stephen R.en_US
dc.date.accessioned2007-04-23T16:38:46Z
dc.date.available2007-04-23T16:38:46Z
dc.date.issued1980-02en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR80-413en_US
dc.identifier.urihttps://hdl.handle.net/1813/6253
dc.description.abstractIn this paper we study languages accepted by nondeterministic $\log n$-tape automata which scan their input only once and relate their computational power to two-way, $\log n$-tape automata. We show that for the one-way, $\log n$-tape automata the nondeterministic model (1-NL) is computationally much more powerful than the deterministic model (1-L); that under one-way, $\log n$-tape reductions there exist natural complete languages for these automata and that the complete languages cannot be sparse. Furthermore, we show that any language complete for nondeterministic one-way $\log n$-tape automata (under 1-L reductions) is also complete for the computationally more powerful nondeterministic two-way, $\log n$-tape reductions. Therefore, for all bounds $T(n),T(n \geq \log n$, the deterministic and nondeterministic $T(n)$-tape bounded computations collapse if the nondeterministic one-way $\log n$-tape computations can be carried out by two-way deterministic $\log n$-tape automata.en_US
dc.format.extent824346 bytes
dc.format.extent368178 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.titleLanguages Simultaneously Complete for One-Way and Two-Way Log-Tape Automataen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics