判断强连通自动机同构的一个多项式时间算法

众所周知,自动机的同构、图的同构等问题是多项式时间等价的(Booth,SIAM J.Comput,7(1978),3)。因此,讨论自动机的同构及其子问题是十分有意义的。最近,李慧陵给出了计算强连通自动机的自同构群的一个多项式时间算法。本文借助于此结果,在固定字母表的情况下,给出了判断两个强连通自动机是否同构的一个多项式时间算法。