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