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 $ \mathfrak A _ {i} = ( A _ {i} , S _ {i} , B _ {i} , \phi _ {i} , \psi _ {i} ) $, $ i = 1 \dots n $, is the automaton $ \mathfrak A = (A, S, B, \phi , \psi ) $ for which

$$ S = S _ {1} \times \dots \times S _ {n} ,\ A = A _ {1} \times \dots \times A _ {n} , $$

$$ B = B _ {1} \times \dots \times B _ {n} , $$

while the functions $ \phi (s, a) $ and $ \psi (s, a) $ are defined by the relations

$$ \phi ( ( s _ {1} \dots s _ {n} ), ( a _ {1} \dots a _ {n} ) ) = $$

$$ = \ ( \phi _ {1} (s _ {1} , a _ {1} ) \dots \phi _ {n} (s _ {n} , a _ {n} )), $$

$$ \psi ( ( s _ {1} \dots s _ {n} ), ( a _ {1} \dots a _ {n} ) ) = $$

$$ = \ ( \psi _ {1} (s _ {1} , a _ {1} ) \dots \psi _ {n} (s _ {n} , a _ {n} )). $$

The superposition of automata $ \mathfrak A _ {1} = (A _ {1} , S _ {1} , B _ {1} , \phi _ {1} , \psi _ {1} ) $ and $ \mathfrak A _ {2} = (B _ {1} , S _ {2} , B _ {2} , \phi _ {2} , \psi _ {2} ) $ is the automaton $ \mathfrak B = (A _ {1} , S, B _ {2} , \phi , \psi ) $ for which $ S = S _ {2} \times S _ {1} $ and

$$ \phi ( ( s _ {2} , s _ {1} ), a ) = ( \phi _ {2} ( s _ {2} , \psi _ {1} ( s _ {1} , a ) ), \phi _ {1} ( s _ {1} , a )), $$

$$ \psi ( ( s _ {2} , s _ {1} ), a ) = \psi _ {2} ( s _ {2} , \psi _ {1} ( s _ {1} , a ) ), $$

where $ (s _ {2} , s _ {1} ) \in S $ and $ a \in A _ {1} $.

In problems of completeness and synthesis of automata the feedback operation is very important. This operation is applicable to automata with $ n $ inputs and $ m $ outputs $ \mathfrak A = (A, S, B, \phi , \psi ) $ where $ A = A _ {1} \times \dots \times A _ {n} $, $ B = B _ {1} \times \dots \times B _ {m} $,

$$ \psi ( s , ( a _ {1} \dots a _ {n} )) = $$

$$ = \ ( \psi _ {1} ( s, ( a _ {1} \dots a _ {n} ) ) \dots \psi _ {m} ( s, ( a _ {1} \dots a _ {n} ) ) ), $$

such that for certain $ i, j $ the relation $ B _ {i} = A _ {j} $ is true and the function $ \psi _ {i} $ is independent of $ a _ {j} $, i.e.

$$ \psi _ {i} = \psi _ {i} ( s, ( a _ {1} \dots a _ {j-1 } , a _ {j+1 } \dots a _ {n} ) ). $$

Under these conditions, the feedback operation on the $ i $- th output and $ j $- th input of automaton $ \mathfrak A $ yields the automaton $ \mathfrak A ^ \prime = (A ^ \prime , S, B, \phi ^ \prime , \psi ^ \prime ) $ such that $ A ^ \prime = A _ {1} \times \dots \times A _ {j-1} \times A _ {j+1} \times \dots \times A _ {n} , $

$$ \phi ^ \prime (s, (a _ {1} \dots a _ {j-1} , a _ {j+1} \dots a _ {n} )) = $$

$$ = \ \phi (s, (a _ {1} \dots a _ {j-1} , $$

$$ {}{} \psi _ {i} (a _ {1} \dots a _ {j-1} , a _ {j+1} \dots a _ {n} ), a _ {j+1} \dots a _ {n} )), $$

$$ \psi ^ \prime (s, (a _ {1} \dots a _ {j-1} , a _ {j+1} \dots a _ {n} )) = $$

$$ = \ \psi (s, ( a _ {1} \dots a _ {j-1} , $$

$$ {}{} \psi _ {i} (s, ( a _ {1} \dots a _ {j-1} , a _ {j+1} \dots a _ {n} )), a _ {j+1} \dots a _ {n} )). $$

There are also other kinds of compositions of automata, e.g. the product, direct sum, semi-direct product, etc.

References

[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)

Comments

For more information see [a1].

References

[a1]	F. Géiseg, "Products of automata" , Springer (1986)