Что: | Лекция |
Когда: | Четверг, 24 октября 2013, 18:30–19:50 |
Где: | ПОМИ РАН |
Автоматные языки и классы эквивалентности. DSpace[1] совпадает с множеством автоматных языков. Лемма о накачке. Пример языка, который не является автоматным, но решается с использованием \( O(\log \log n) \) памяти. DSpace[\( o(\log \log n) \)]=DSpace[1]. Теорема Савича: достижимость в неориентированном графе решается с использованием \( O(\log^2 n) \) памяти.