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