SYNTHESIS OF AUTOMATA BY DECOMPOSITION TECHNIQUES.
Final rept., Mar 65-Sep 66,
STANFORD RESEARCH INST MENLO PARK CA
Pagination or Media Count:
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
- Operations Research