Deterministic one-way Turing machines with sublinear space

DOI10.3233/FI-2015-1147MaRDI QIDQ2805402zbMATH OpenOpenAlexFDO

Authors Martin Kutrib, Julien Provillard, Matthias Wendlandt, György Vaszil

Publication date 11 May 2016

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2015-1147

zbMATH Keywords

\(P\) automataspace boundTuring machine

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Weak and strong one-way space complexity classes
• Computational power of one-way Turing machines with sublogarithmic memory restrictions
• scientific article; zbMATH DE number 3887666
• scientific article; zbMATH DE number 3858415
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties

Cited in

(7)

• Deterministic Turing machines in the range between real-time and linear-time.
• Element distinctness on one-tape Turing machines: a complete solution
• Computational power of one-way Turing machines with sublogarithmic memory restrictions
• A space lower bound for acceptance by one-way _2-alternating machines
• Weak and strong one-way space complexity classes
• scientific article; zbMATH DE number 3858415 (Why is no real title available?)
• scientific article; zbMATH DE number 5593330 (Why is no real title available?)

This page was built for publication: Deterministic one-way Turing machines with sublinear space

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