The problem of deciding if a given function of the set of states of a finite automation A belongs to its input semigroup is known to be PSPACE-complete. However, many other decision problems with regard to the input semigroup of A have polynomial time solutions. In particular, it is decidable whether a given automation is isomorphic to its own monoid automation, and whether its input semigroup contains an identity, or is a group. By analysis of the ranges and domain partitions of input functions of an automation, combined with known necessary and sufficient conditions for homomorphisms on singly generated automata, regularity on the structure of the semigroup automation is established and significant improvement is made to decision algorithms for the semigroups of automata.
