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