[math-fun] Complexity of detecting whether the intersection of two regular languages is empty?
Given two regular expressions, how hard is it to tell whether they unify, i.e. whether the intersection of the languages they denote is empty? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Not too hard, since the intersection of two regular languages means the set of strings accepted by two finite-state automata, and this pair can be simulated by a single larger finite-state automaton. However, the number of states of this automaton is the product of the number of states the two automata have. - Cris
On Nov 30, 2017, at 1:32 PM, Mike Stay <metaweta@gmail.com> wrote:
Given two regular expressions, how hard is it to tell whether they unify, i.e. whether the intersection of the languages they denote is empty?
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Aha! This python library does the job: https://qntm.org/greenery
from greenery.lego import parse print(parse("abc...") & parse("...def")) abcdef print(parse("\d{4}-\d{2}-\d{2}") & parse("19.*")) 19\d\d-\d\d-\d\d print(parse("\W*") & parse("[a-g0-8$%\^]+") & parse("[^d]{2,8}")) [$%\^]{2,8} print(parse("[bc]*[ab]*") & parse("[ab]*[bc]*")) ([ab]*a|[bc]*c)?b* print(parse("a*") & parse("b*")) # returns empty string, the one string they both match
print(parse("a") & parse("b")) # returns empty character class []
As Victor pointed out, it can be very expensive to compute the intersection. I learned it's because at one point you're converting an NFA to a DFA, which can be exponentially large. On Thu, Nov 30, 2017 at 1:42 PM, Cris Moore <moore@santafe.edu> wrote:
Not too hard, since the intersection of two regular languages means the set of strings accepted by two finite-state automata, and this pair can be simulated by a single larger finite-state automaton. However, the number of states of this automaton is the product of the number of states the two automata have.
- Cris
On Nov 30, 2017, at 1:32 PM, Mike Stay <metaweta@gmail.com> wrote:
Given two regular expressions, how hard is it to tell whether they unify, i.e. whether the intersection of the languages they denote is empty?
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
This blog post discusses this: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-auto... . In particular, Dexter Kozen proved that finding the intersection of two finite state automata (nondeterministic) is PSPACE complete. On the other hand, if the automata are deterministic, you can with m and n states respectively, the automaton which is their intersection has m*n states, and reducing it to canonical form takes at most m*n*log(m*n), though, if you just want to test emptiness, I believe that you can dispense with the log term. Victor On Thu, Nov 30, 2017 at 3:32 PM, Mike Stay <metaweta@gmail.com> wrote:
Given two regular expressions, how hard is it to tell whether they unify, i.e. whether the intersection of the languages they denote is empty?
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Thu, Nov 30, 2017 at 4:17 PM, Victor Miller <victorsmiller@gmail.com> wrote:
This blog post discusses this: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-auto...
A very interesting article, but it says nothing about nondeterministic finite automata; everything in the article is about deterministic automata. The focus of the article is whether there are algorithms for determining whether the intersection is empty that are faster than constructing the product automata; if you want to intersect k automata with n states each, can you do this in time less than n^k?
. In particular, Dexter Kozen proved that finding the intersection of two finite state automata (nondeterministic) is PSPACE complete.
This seems wrong. Just as with deterministic automata, if you have an NDFA with m states, and another with n states, you can construct a product NDFA with m*n states. Determining whether the intersection is nonempty is just determining whether this automaton accepts a non-empty language, This can certainly be done in time linear in the number of edges in the graph, which is quadratic in the number of vertices, so if this is PSPACE complete, then P = PSPACE. What am I missing?
Whoops, I was wrong. Kozen showed that to find if the intersection of k automata accepts the empty language is PSPACE complete. The straightforward way would take time n^k (if each was a DFA had n states). I actually ran into this as a practical problem a few years ago, and was wondering if there was a more clever way to do it. Dexter was a friend and colleague from my IBM days, and he set me straight. Victor On Thu, Nov 30, 2017 at 4:33 PM, Andy Latto <andy.latto@pobox.com> wrote:
On Thu, Nov 30, 2017 at 4:17 PM, Victor Miller <victorsmiller@gmail.com> wrote:
This blog post discusses this: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite- automata/
A very interesting article, but it says nothing about nondeterministic finite automata; everything in the article is about deterministic automata. The focus of the article is whether there are algorithms for determining whether the intersection is empty that are faster than constructing the product automata; if you want to intersect k automata with n states each, can you do this in time less than n^k?
. In particular, Dexter Kozen proved that finding the intersection of two finite state automata (nondeterministic) is PSPACE complete.
This seems wrong. Just as with deterministic automata, if you have an NDFA with m states, and another with n states, you can construct a product NDFA with m*n states. Determining whether the intersection is nonempty is just determining whether this automaton accepts a non-empty language, This can certainly be done in time linear in the number of edges in the graph, which is quadratic in the number of vertices, so if this is PSPACE complete, then P = PSPACE.
What am I missing?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Thu, Nov 30, 2017 at 2:33 PM, Andy Latto <andy.latto@pobox.com> wrote:
On Thu, Nov 30, 2017 at 4:17 PM, Victor Miller <victorsmiller@gmail.com> wrote:
. In particular, Dexter Kozen proved that finding the intersection of two finite state automata (nondeterministic) is PSPACE complete.
This seems wrong. Just as with deterministic automata, if you have an NDFA with m states, and another with n states, you can construct a product NDFA with m*n states. Determining whether the intersection is nonempty is just determining whether this automaton accepts a non-empty language, This can certainly be done in time linear in the number of edges in the graph, which is quadratic in the number of vertices, so if this is PSPACE complete, then P = PSPACE.
What am I missing?
Hmm, good point. If you don't convert the NFAs to DFAs and you're only trying to detect whether the intersection is empty, not determine the intersection language, then it looks like the problem is much easier. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
On Thu, Nov 30, 2017 at 3:02 PM, Mike Stay <metaweta@gmail.com> wrote:
On Thu, Nov 30, 2017 at 2:33 PM, Andy Latto <andy.latto@pobox.com> wrote:
On Thu, Nov 30, 2017 at 4:17 PM, Victor Miller <victorsmiller@gmail.com> wrote:
. In particular, Dexter Kozen proved that finding the intersection of two finite state automata (nondeterministic) is PSPACE complete.
This seems wrong. Just as with deterministic automata, if you have an NDFA with m states, and another with n states, you can construct a product NDFA with m*n states. Determining whether the intersection is nonempty is just determining whether this automaton accepts a non-empty language, This can certainly be done in time linear in the number of edges in the graph, which is quadratic in the number of vertices, so if this is PSPACE complete, then P = PSPACE.
What am I missing?
Hmm, good point. If you don't convert the NFAs to DFAs and you're only trying to detect whether the intersection is empty, not determine the intersection language, then it looks like the problem is much easier.
Nope, I'm wrong. Here's the Kozen paper: www.cs.cornell.edu/~kozen/papers/LowerBounds.pdf Lemma 3.2.3 is the relevant bit. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (4)
-
Andy Latto -
Cris Moore -
Mike Stay -
Victor Miller