scientific article; zbMATH DE number 2077107

MaRDI QIDQ4470489zbMATH OpenFDO

Authors Martin Dietzfelbinger, Martin Hühne

Publication date 1 July 2004

zbMATH Keywords

Turing machine

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
• scientific article; zbMATH DE number 17549
• Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
• The complexity of on-line simulations between multidimensional turing machines and random access machines
• Linear-time simulation of multihead Turing machines

Cited in

(6)

• Simulation of three-dimensional one-marker automata by five-way Turing machines
• Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
• Linear-time simulation of multihead Turing machines
• Mutual upper bounds of size and time for a Turing machine and a Markov-Post algorithm for mutual simulations
• ZUR RAUMKOMPLIZIERTHEIT MEHRDIMENSIONALER TURING‐AUTOMATEN
• scientific article; zbMATH DE number 17549 (Why is no real title available?)

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 Q4470489)