scientific article; zbMATH DE number 3988711

zbMATH Open0611.68023MaRDI QIDQ3751009FDOQ3751009

Authors: Wolfgang Maass, Georg Schnitger 

Publication date: 1986

Title of this publication is not available (Why is that?)

Recommendations

• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• scientific article; zbMATH DE number 17549
• Bounds for the Element Distinctness Problem on one-tape Turing machines
• Theory of one-tape linear-time Turing machines
• scientific article; zbMATH DE number 5593330
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• Two tapes versus one for off-line Turing machines
• Two Tapes are Better than One for Nondeterministic Machines
• scientific article; zbMATH DE number 3984575

zbMATH Keywords

sortingoffline 1-tape Turing machinestransposing a matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (9)

• A space lower bound for acceptance by one-way \(\Pi_2\)-alternating machines
• k\(+1\) heads are better than k for PDAs
• The speed of copying on one-tape off-line turing machines
• Two tapes versus one for off-line Turing machines
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• Title not available (Why is that?)
• The complexity of matrix transposition on one-tape off-line Turing machines
• Transposition of an \(\ell \times \ell\) matrix requires \(\Omega\) (log \(\ell)\) reversals on conservative Turing machines
• The complexity of matrix transposition on one-tape off-line Turing machines with output tape

This page was built for publication:

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