Results on homomorphic realization of automata by \(\alpha_ 0\)-products (Q1177141)

There are two traditions in the structure theory of automata which differ already in the ways an automaton can realize another: one allows input letters to be coded as arbitrary words while the other insists on letter- to-letter codings. The former approach rests on semigroup theory and has culminated in the Krohn-Rhodes decomposition theory and some applications in formal language theory. The second approach uses methods of universal algebra and lattice theory, and it has been widely applied in sequential circuit theory. \{The reviewer does not share the author's view of the relative successes of the two approaches.\} Here an intermediate notion of divisibiity is considered: a semigroup \(S\) divides an automaton \(\mathbf A\) `in equal lengths' if there exists a homomorphism from a subsemigroup of the characteristic semigroup \(S({\mathbf A})\) into \(S\) such that every element of \(S\) has a preimage defined by an input word of some fixed length (there are actually two versions of the concept). The main result of the paper is that irreducibility with respect to this divisibility concept is equivalent to irreducibility in the sense of Krohn and Rhodes. Moreover, some completeness questions are considered.