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

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