Two-Way Automata Versus Logarithmic Space |
| |
Authors: | Christos A Kapoutsis |
| |
Affiliation: | 1. LIAFA, Université Paris Diderot—Paris VII, Case 7014, 75205, Paris Cedex 13, France
|
| |
Abstract: | We strengthen a previously known connection between the size complexity of two-way finite automata ( ) and the space complexity of Turing machines (tms). Specifically, we prove that every s-state has a poly(s)-state that agrees with it on all inputs of length ≤s if and only if NL?L/poly, and every s-state has a poly(s)-state that agrees with it on all inputs of length ≤2 s if and only if NLL?LL/polylog. Here, and are the deterministic and nondeterministic , NL and L/poly are the standard classes of languages recognizable in logarithmic space by nondeterministic tms and by deterministic tms with access to polynomially long advice, and NLL and LL/polylog are the corresponding complexity classes for space O(loglogn) and advice length poly(logn). Our arguments strengthen and extend an old theorem by Berman and Lingas and can be used to obtain variants of the above statements for other modes of computation or other combinations of bounds for the input length, the space usage, and the length of advice. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|