space complexity of DFA intersection problem 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 &amp; L vs P / cstheory SE
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.  :)