Deterministic one-way Turing machines with sublinear space

DOI10.3233/FI-2015-1147zbMATH Open1339.68082OpenAlexW1580502441MaRDI QIDQ2805402FDOQ2805402

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

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

zbMATH Keywords

Turing machinespace bound\(P\) automata

Mathematics Subject Classification ID

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

Cited In (6)

• A space lower bound for acceptance by one-way \(\Pi_2\)-alternating machines
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

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)