Множество регулярных языков совпадает с DSpace[1]. DSpace[\(\log \log n\)] содержит нерегулярные языки, а DSpace[\(o(\log \log n)\)]=DSpace[1]. Теорема Савича: Проверить наличие пути в ориентированном графе можно, используя \(\log^2 n\) памяти, PSPACE=NPSPACE.

Текущая версия конспекта.