DECOMPOSITION THEORY OF SEMIAUTOMATA AND AUTOMATA.

The report is divided in three parts. Part A establishes a general algebraic theory of semi-automata and automata decompositions. Homomorphic relations and their applications to transition graphs are considered. These relations extend the concept of homomorphic functions, and suitably generalize well known results on partitions having the substitution property and quotient algebras. Both completely and incompletely specified transition graphs are considered. The relationship between automata behavior and the algebraic structure of their semi-automata is considered. The final section of Part A relates cascade decompositions of automata involving two or more components to the algebraic structure of their semi-automata. Part B discusses various aspects of cascade-decomposition techniques for Mealy automata. An attempt is made to combine the engineering viewpoint of the decomposition theory of Hartmanis and Stearns with the mathematically elegant but uneconomical decomposition theory of Krohn and Rhodes. New results are obtained on the proper selection of a tail machine. Efficient techniques for the cascade decomposition of some classes of semi-automata are discussed. Further research in this direction appears very promising. Part C discusses state splitting for single input machines. A concept of a useful split is introduced. Criteria for a transformation graph to have a useful split or to have only useless splits are developed. Author