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