DOIAbstract
A series-parallel decomposition of an automaton A into r components (r ⩾ 1) is said to be practical if every component has fewer states than the original automaton A. It is said to be perfect iff the product of the numbers of states of components is equal to the number of states of A. Necessary and sufficient conditions are given for a Moore-type automaton to have a practical decomposition. An algebraic criterion is also given for a reduced, strongly connected permutation automaton to have a perfect decomposition. It should be noted that an automaton may have a perfect decomposition although its semigroup is a simple group, and that an automaton may not have a practical decomposition, while its semigroup is a nonsimple group
Add to ORKG