SYNTHESIS OF AUTOMATA BY DECOMPOSITION TECHNIQUES.

Abstract : The major effort under this research program was devoted to parallel decompositions of single-input automata (autonomous sequential machines) without and with state-splitting. First, decompositions into two smaller automata subject to suitable optimality criteria were considered and computational decomposition techniques were established. Next, indecomposable single-input automata (modules) were characterized and methods were derived for the realization of any specified single-input automaton as parallel composition of such modules. Some results concerning cascade decompositions of single-input automata are also given. The other part of this research program was devoted to establishing a mathematically precise, basic theory for generalized cascade decompositions of partially specified multi-input semi-automata (output-free sequential machines). Earlier work by Yoeli was unified with recent work on complete automata by Zeiger. The concept of homomorphic relation plays an important role in this connection. (Author)