Next: Automata with memory Up: What to look Previous: Factor automata

# Product automata

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 .

Next: Automata with memory Up: What to look Previous: Factor automata

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx