Two-way automata versus logarithmic space
From MaRDI portal
Publication:2254505
DOI10.1007/s00224-013-9465-0zbMath1319.68135MaRDI QIDQ2254505
Publication date: 5 February 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-013-9465-0
two-way finite automata; logarithmic space; Sakoda-Sipser conjecture; 2D versus 2N; L versus NL; sub-logarithmic space
68Q45: Formal languages and automata
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)