Show simple item record

dc.contributor.authorHartmanis, Jurisen_US
dc.contributor.authorMahaney, Stephen R.en_US
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.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


This item appears in the following Collection(s)

Show simple item record