一个求强连通自动机的自同构群的多项式算法

在本文中,所谓自动机是指一个体系(?)=(S,∑),其中S为一个集合,其元素称为状态,∑为一个集合,其元素称为字母,并且对任何s∈S和σ∈∑,都有一个状态与之对应,并记作s~σ。∑的字母的有限序列称为字。称(?)是强连通的,如果对任何两个状态s,s′∈S都有∑上的字ω=σ_1σ_2…σ_i,使s~ω=s′,其中s~ω=(((s~(σ_1)~σ_2)…)~σ_t。称S到自身的一个1-1映