4
$\begingroup$

the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper significance in computational complexity theory.[1][2] it is O(n2) time with no better lower bounds known, and tight bounds possibly having major implications on multiple complexity class separations. looking for insight/ refs.

what is the best known space complexity of determining DFA intersection (emptiness)? how does the best known algorithm work?

[1] Deciding emptiness of intersection of regular languages in subquadratic time / cstheory SE
[2] Two DFA intersection emptiness connections to SETH & L vs P / cstheory SE

$\endgroup$
7
$\begingroup$

Solving intersection Non-Emptiness for 2 DFA's:

It essentially just becomes a reachability problem for the product DFA.

  • Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ space.

  • Or, we can solve it non-deterministically with $O(\log(n))$ space.

  • By Savitch's Theorem, we can also solve it deterministically in $2^{O(\log^2(n))}$ time using $O(\log^2(n))$ space.

To the best of my knowledge, it is not known if we can solve it deterministically in polynomial time using $O(n^{2-\epsilon})$ space.

Feel free to share any thoughts or ideas in the comments. :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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