Two Tapes are Better than One for Nondeterministic Machines

DOI10.1137/0213016MaRDI QIDQ3347301zbMATH OpenOpenAlexFDO

Authors 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

Recommendations

• Alternating real-time computations
• On two-tape real-time computation and queues
• Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
• scientific article; zbMATH DE number 2068877
• scientific article; zbMATH DE number 3984575

Cited in

(16)

• Theory of one-tape linear-time Turing machines
• 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
• Two heads are better than two tapes
• Single-tape reset machines
• scientific article; zbMATH DE number 3943032 (Why is no real title available?)
• scientific article; zbMATH DE number 3976379 (Why is no real title available?)
• scientific article; zbMATH DE number 3980489 (Why is no real title available?)
• scientific article; zbMATH DE number 3984575 (Why is no real title available?)
• scientific article; zbMATH DE number 3988711 (Why is no real title available?)
• Uniform simulations of nondeterministic real time multitape turing machines
• Two heads are better than two tapes
• Pushdown store machines and real-time computation
• On two-tape real-time computation and queues

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3347301)