A characterization of automata and a direct product decomposition

摘要

The classes of automata characterized by certain semigroups are investigated: It isshown that the classes of cyclic quasi-state-independent automata, cyclic quasi-state-independent automat of monoid type, cyclic Abelian automata, strongly connected state-independent automata, strongly connected resect automata, quasi-perfect automata, and perfect automata are equivalent to the classes of automata generated by semigroups with left identity, monoids, commutative semigroups with identity, right groups, right zero semigroups, groups, and Abelian groups, respectively. The characterization of the endomorphism semigroups and the automorphism groups and the direct product decomposabilities for the above classes of automata are also given. Finally, it is shown that every regular set can be accepted by some cyclic quasi-state-independent acceptor of monoid type.