Fooling Turing machines with sublogarithmic space: a note on `For completeness, sublogarithmic space is no space' by M. Agrawal

DOI10.1016/J.IPL.2007.11.005zbMATH Open1186.68202OpenAlexW2039922144MaRDI QIDQ963359FDOQ963359

Authors: Andrzej Szepietowski 

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.11.005

zbMATH Keywords

computational complexitysublogarithmic space

Mathematics Subject Classification ID

Cites Work

• Turing machines with sublogarithmic space
• The alternation hierarchy for sublogarithmic space is infinite
• A hierarchy that does not collapse : alternations in low level space
• For completeness, sublogarithmic space is no space.

This page was built for publication: Fooling Turing machines with sublogarithmic space: a note on `For completeness, sublogarithmic space is no space' by M. Agrawal

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