patternMinor
space complexity of DFA intersection problem
Viewed 0 times
problemdfaspaceintersectioncomplexity
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 & L vs P / cstheory SE
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
Solution
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. :)
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. :)
Context
StackExchange Computer Science Q#49234, answer score: 9
Revisions (0)
No revisions yet.