Two Tapes are Better than One for Nondeterministic Machines

DOI10.1137/0213016zbMath0558.68045OpenAlexW1981106003MaRDI QIDQ3347301

Pavol Ďuriš, Zvi Galil

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213016

zbMATH Keywords

computational power of real-time nondeterministic Turing machinesreversal-bounded machinessingle working tapetwo pushdown storestwo working tapes

Mathematics Subject Classification ID

Related Items (5)

On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ Tape versus queue and stacks: The lower bounds ⋮ Alternating real-time computations ⋮ Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time ⋮ Theory of one-tape linear-time Turing machines

This page was built for publication: Two Tapes are Better than One for Nondeterministic Machines