Element Distinctness and Sorting on One-Tape Off-Line Turing Machines

DOI10.1007/978-3-540-77566-9_35MaRDI QIDQ5448667zbMATH OpenOpenAlexFDO

Authors Holger Petersen

Publication date 7 March 2008

Published in SOFSEM 2008: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77566-9_35

Mathematics Subject Classification ID

Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Sorting and Element Distinctness on One-Way Turing Machines
• The element distinctness problem on one-tape Turing machines
• Element distinctness on one-tape Turing machines: a complete solution
• Bounds for the Element Distinctness Problem on one-tape Turing machines
• scientific article; zbMATH DE number 5593330
• The complexity of matrix transposition on one-tape off-line Turing machines
• scientific article; zbMATH DE number 4060710
• The complexity of matrix transposition on one-tape off-line Turing machines with output tape
• scientific article; zbMATH DE number 17549

Cited in

(5)

• Bounds for the Element Distinctness Problem on one-tape Turing machines
• Element distinctness on one-tape Turing machines: a complete solution
• Sorting and Element Distinctness on One-Way Turing Machines
• A Time-Space Tradeoff for Element Distinctness
• The element distinctness problem on one-tape Turing machines

This page was built for publication: Element Distinctness and Sorting on One-Tape Off-Line Turing Machines

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