New answers tagged

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