A space \((o(\log\log n))\) is regular. (English) Zbl 0767.68039

Summary: One of the common results of resource bounded Turing machines is the \(\log\log n\) lower bound for the space usage of deterministic and nondeterministic Turing machines that accept nonregular languages. This result is extended to alternating Turing machines: It is proved that if \(f(n)=o(\log\log n)\), then \(f(n)\)-space-bounded (off-line) alternating Turing machines can accept only regular sets. The problem has been open for a decade.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
Full Text: DOI