半群乘法表的构作及其复杂度

Construction of the Multiplication Table of the Semigroup and Its Complex Degree

本文证明了,对于一个有限生成半群,如果它的生成关系是完备的,则可以在多项式时间内机械地判定半群是砂为有限半群,并且在半群有限时,可以构作其乘法法,进而判定该半群的许多代数性质.

In this paper,we have proved that for a finitely generated scmigroup with complete gen-erating relation we can mechanically decide if the semigroup in polynomial time is finite andwhen the semigroup is finite.Wwe can construct its multiplication table,and then decidemany algebraic properties of the semigroup.