Investigating Reversible Cellular Automata with Evolutionary Algorithms


Cellular Automata (CA) are one of the oldest natural computing models studied in the literature, and nowadays they find applications in a wide range of domains, both as a tool for simulating complex dynamical systems and for implementing efficient computational devices in hardware. In this respect, Reversible Cellular Automata (RCA) represent an interesting breed of CA, since their dynamics consists only of disjoint cycles. While most of the studies concerning RCA usually rely on system-theoretic or algebraic methods to characterize specific classes of RCA, in this talk we overview a new approach which is based on the use of Evolutionary Algorithms (EA). We give an overview of recent results about the use of EA to investigate RCA whose local rules are defined by conserved landscapes, a class that has received little attention in the literature. In particular, we emphasize that genetic algorithms (GA) and genetic programming (GP) can be a useful tool to discover interesting properties of this type of RCA, such as the trade-off between the reversibility of a local rule and its Hamming weight, which has an impact on their applicability in cryptography.

Invited Seminar for the Electronic and Computer Engineering Department
University of Trieste, Italy