[Solved]: What is the complexity of the emptiness problem for 2-way DFAs?

Problem Detail: 

I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape.

According to Wikipedia, they are equivalent to DFAs, though the equivalent DFA might be exponentially larger. I've found state complexity for their complements and intersections, but not for their emptiness-testing.

Does anyone know of a paper where I could find this?

Asked By : jmite

Answered By : Hendrik Jan

Friend Google suggests the following "The PSPACE-completeness of the emptiness problem for two-way deterministic finite-state automata in Exercise 5.5.4 is due to Hunt (1973)." (An Introduction to the Theory of Computation, Eitan Gurari, Computer Science Press, 1989, online)

Hunt, H. (1973). "On the time and tape complexity of languages," Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 10-19.

(I have now looked at the reference) The paper is written in an abstract way as you note. The crucial part for us is the proof of Thm 3.7, where it is suggested that one can construct a 2FSA $\cal A$ that accepts valid computations of a linear bounded automaton $\cal M$ on a fixed(!) string $x$ (which is close to the definition of PSPACE). The 2FSA $\cal A$ is constructable in polynomial time (in the size of $\cal M$ and $x$). A computation of a LBA can be written as $x\$x_1\$\dots\$x_n$ where the $x_i$ are all of the same length as $x$ and are consecutive steps of $\cal M$. How does $\cal A$ check that $x_i$ and $x_{i+1}$ are equal (up to a very local change of a state and a single symbol as the operation of a LBA)? By checking letter by letter, going both ways on the tape. For that we need a counter of size $|x|$ implemented in the finite state control of $\cal A$.

It turns out that the problem is mentioned in the appendix of the classic reference by Garey & Johnson, Computers and Intractability, problem [AL2] "Two-way finite state automaton non-emptiness" with the explicit remark "PSPACE-complete even if $\cal A$ is deterministic". Reference again Hunt, with the clarification "Transformation from Linear Bounded Automaton Acceptance" (Given LBA $\cal A$ and input $x$, does $\cal A$ accept $x$?). The latter problem is [AL3] with reference to the famous Karp (1972) paper "Reducibility Among Combinatorial Problems" (where LBA Acceptance is mentioned as Context-Sensitive Recognition).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13456