有限自动机上几个问题的复杂性分析

凡多项式时间等价于图同构检验的问题称为同构完全问题.本文证明了,强连通自动机同构检验问题、自动机强同构检验问题、自动机自同构问题和自动机的自同构群的阶问题是同构完全的。