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.005zbMath1186.68202OpenAlexW2039922144MaRDI QIDQ963359

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

• The alternation hierarchy for sublogarithmic space is infinite
• Turing machines with sublogarithmic space
• For completeness, sublogarithmic space is no space.
• A hierarchy that does not collapse : alternations in low level 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