Additive Automata On Graphs
Klaus Sutner
Stevens Institute of Technology, Hoboken, NJ 07030, USA
Abstract
We study cellular automata with additive rules on finite undirected graphs. The addition is carried out in some finite abelian monoid. We investigate the problem of deciding whether a given configuration has a predecessor. Depending on the underlying monoid this problem is solvable in polynomial time or NP-complete. Furthermore, we study the global reversibility of cellular graph automata based on addition modulo two. We give a linear time algorithm to decide reversibility of unicyclic graphs.
