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