are_isomorphic() can raise false negatives
The two following automata are isomorphic but canonicalize()
gives them a different canonical form, leading are_isomorphic()
to answer false
.
The same signature is computed for states 1, 2 and 3, so they end up in the same equivalence class and are not remapped as they should.
This bug was found after @max noted that are_isomorphic()
is either incorrect, or solves the graph isomorphism problem in polynomial time.