Automata, composition of

From Encyclopedia of Mathematics
Jump to: navigation, search

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.


[1] 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
[2] 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)
How to Cite This Entry:
Automata, composition of. V.N. Red'ko (originator), Encyclopedia of Mathematics. URL:,_composition_of&oldid=15462
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098