4
$\begingroup$

We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way finite state automaton is also PSpace-complete.

Is there anything known about checking the emptiness of intersection of an unbounded number of two-way state automata? Maybe even deterministic ones.

Googling did not give anything. But maybe some hypothesis/connection with other problems/etc.?

$\endgroup$

1 Answer 1

6
$\begingroup$

Unlike one-way models, intersection of 2-way NFAs is "cheap": Given 2-way NFAs $A_1,A_2$, you can construct a 2-way NFA $B$ for their intersection that works as follows: it first behaves like $A_1$, and once the accepting state is reached, it resets the head to the left marker (using a single state), and starts at the initial state of $A_2$.

This can be easily extended to any number of NFAs, and the construction has linear size.

Thus, the non-emptiness problem for intersection of 2-way NFAs reduces to non-emptiness of a single 2-way NFA. So still PSPACE-complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.