Complexity of nondeterministic multitape computations based on crossing sequences

DOI10.1007/978-3-642-22600-7_25MaRDI QIDQ5200101zbMATH OpenOpenAlexFDO

Authors Jiří Wiedermann

Publication date 29 July 2011

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22600-7_25

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3982519
• scientific article; zbMATH DE number 5593330
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• A speed-up theorem without tape compression
• scientific article; zbMATH DE number 3984575

Cites work

• Computational Complexity of One-Tape Turing Machine Computations
• Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3628391 (Why is no real title available?)
• scientific article; zbMATH DE number 1222596 (Why is no real title available?)
• scientific article; zbMATH DE number 2102763 (Why is no real title available?)
• scientific article; zbMATH DE number 5593330 (Why is no real title available?)
• On Time Versus Space
• One-tape, off-line Turing machine computations
• Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM’<scp>s</scp>
• Tape bounds for time-bounded Turing machines
• Time- and tape-bounded Turing acceptors and AFLs

This page was built for publication: Complexity of nondeterministic multitape computations based on crossing sequences

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