On the Transformation Semigroups of Finite Automata

摘要

Necessary and sufficient conditions for a given automaton to be of left identity type, of identity type, of right group type, of group type quasi state independent, and state independent are presented. The time required to decide whether or not each condition holds for a given automaton is also estimated under the uniform cost criterion. In addition, it is shown that there exists a one-input automaton whose transformation semigroup has its order greater than any polynomial function of the number of states and that the index and the period of the transformation semigroup of a one-input automaton can be determined in time proportional to the number of states. A one-input automaton with the minimum number of states such that its transformation semigroup is isomorphic to a given cyclic one is also discussed.