The complexity of computing the automorphism group of automata and related problems
Zhang Shuhua, Li Lian · International Journal of Computer Mathematics · 1988
A polynomial time algorithm for computing the automorphism group of cyclic automata is given. The problems of computing the automorphism group of automata, testing either two graphs, two strongly connected automata for isomorphism, or two automata for strong-isomorphism are shown to be polynomially equivalent.