Deterministic one-way Turing machines with sublinear space

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

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

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

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 (4)

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

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)