Automata Theory - Connection To Category Theory

Connection To Category Theory

One can define several distinct categories of automata following the automata classification into different types described in the previous section. The mathematical category of deterministic automata, sequential machines or sequential automata, and Turing machines with automata homomorphisms defining the arrows between automata is a Cartesian closed category, it has both categorical limits and colimits. An automata homomorphism maps a quintuple of an automaton A_i onto the quintuple of another automaton A_j. Automata homomorphisms can also be considered as automata transformations or as semigroup homomorphisms, when the state space,S, of the automaton is defined as a semigroup S_g. Monoids are also considered as a suitable setting for automata in monoidal categories.

Categories of variable automata

One could also define a variable automaton, in in the sense of Norbert Wiener in his book on "Human Use of Human Beings" via the endomorphisms . Then, one can show that such variable automata homomorphisms form a mathematical group. In the case of non-deterministic, or other complex kinds of automata, the latter set of endomorphisms may become, however, a variable automaton groupoid. Therefore, in the most general case, categories of variable automata of any kind are categories of groupoids or groupoid categories. Moreover, the category of reversible automata is then a 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.