Commutativity of Composition of some n-Dimensional Cellular Automata on Monoids

Abstract

The local function of a cellular automaton with binary states can be expressed by a formula in propositional logic. If a local function is that of any reversible cellular automaton, its inverse function can also be expressed as a propositional logic formula, and using it as a local function, we can define the cellular automaton. The multiplication of these formulae in propositional logic yields the local function of the composition of two cellular automata.

In this paper, we consider logical formulae on a commutative monoid as the local functions of n-dimensional cellular automata. We discuss the commutativity of the multiplication of formulae and show some conditions for formulae to satisfy the commutativity of the composition of n-dimensional cellular automata.