Accession Number:

AD0641672

Title:

SYNTHESIS OF AUTOMATA BY DECOMPOSITION TECHNIQUES.

Descriptive Note:

Final rept., Mar 65-Sep 66,

Corporate Author:

STANFORD RESEARCH INST MENLO PARK CA

Personal Author(s):

• Ablow, Clarence M.
• Yoeli, Michael

Report Date:

1966-09-01

Pagination or Media Count:

19.0

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

Descriptors:

• *MATHEMATICAL LOGIC
• SYNTHESIS
• AUTOMATA
• GRAPHICS
• ARTIFICIAL INTELLIGENCE
• ALGEBRA
• QUADRATIC PROGRAMMING

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE