Automata, composition of
Operations by which more complex automata are obtained from other automata by combining the initial automata in accordance with certain rules. Composition of automata plays an important role in problems of synthesis and decomposition of automata. The most important and the most frequently used compositions of automata are the direct product, superposition and feedback.
The direct product of automata , , is the automaton for which
while the functions and are defined by the relations
The superposition of automata and is the automaton for which and
where and .
In problems of completeness and synthesis of automata the feedback operation is very important. This operation is applicable to automata with inputs and outputs where , ,
such that for certain the relation is true and the function is independent of , i.e.
Under these conditions, the feedback operation on the -th output and -th input of automaton yields the automaton such that
There are also other kinds of compositions of automata, e.g. the product, direct sum, semi-direct product, etc.
|||V.M. Glushkov, "The abstract theory of automata" Russian Math. Surveys , 16 : 5 (1961) pp. 1–53 Uspekhi Mat. Nauk , 16 : 5 (1961) pp. 3–62|
|||V.B. Kudryavtsev, "On the cardinality of sets of pre-complete sets of certain function systems, related to automata" Problemy Kibernet. (1965) pp. 45–74 (In Russian)|
For more information see [a1].
|[a1]||F. Géiseg, "Products of automata" , Springer (1986)|
Automata, composition of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automata,_composition_of&oldid=15462