The identification of subautomata and factor automata is an analytic process, in which structure is to be sought in a previously existing system. Synthesis, the converse process, seeks to build up more complex objects by combining simpler parts in prescribed ways. The most common synthetic procedure is to try to endow a cartesian product with structure analogous to that of its constituents. As would be expected, the process works well with automata.

Suppose that **A** is one automaton, with transition function
, and that **B** is a second, with transition function ,
and that is a pair of states. We could define the new
transition function for paired states by setting

In other words, corresponding members of the pairs are neighbors of one another, and transitions in the two halves take place independently, even according to different rules if such is the case.

With pairs for states, a common neighborhood width, and the product
transition function, we have created a new automaton, which
is called the product (or cartesian product) of the two automata **A**
and **B**. Although the definition given applies to **r=1**, a similar
definition would apply for automata with wider neighborhoods. It is
apparent that such definitions multiply the number of states in the
automaton, while keeping the same neighborhoods. Thus, a automaton would really be a automaton, if the
states were relabelled properly.

Two applications of product automata come to mind at once. One is to
see how the same data evolves according to two different automata; we
would set **x=y** to see simultaneous evolution by two different rules.
The second is to set **A=B**, to see how different initial data evolve for
one single automaton.

It is a standard result of structure theory that a product automaton has factor automata corresponding to each of the two automata used to construct it, and that their equivalence relations are complementary. Likewise, we would want to use the notation .

E-mail:mcintosh@servidor.unam.mx