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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1966
- Accession Number
- AD0641672
Entities
People
- Clarence M. Ablow
- Michael Yoeli
Organizations
- SRI International