New answers tagged automata-theory
8
If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex of $D$ and every arc of $D$. For every arc $u \rightarrow v$ of $D$, add the arcs: $uv \rightarrow u$ and $uv \rightarrow v$ in $D’$ (in this order). Clearly $D’$...
0
This paper claims to provide minimized NFA in linear time: https://www.tandfonline.com/doi/abs/10.1080/03057920412331272153
Top 50 recent answers are included
