Isomorphic Classification of First Degree Cellular Automata

Vicky Vikrant
Kamalika Bhattacharjee
Department of Computer Science and Engineering
National Institute of Technology
Tiruchirappalli, Tamil Nadu-620015, India
Sukanya Mukherjee
Department of Computer Science and Engineering
Institute of Engineering and Management
Kolkata, 700091, West Bengal, India

Abstract

This paper explores the concept of isomorphism in cellular automata (CAs), focusing on identifying and understanding isomorphic relationships between distinct CAs. A cellular automaton (CA) is said to be isomorphic to another CA if the configuration transition diagrams of the two CAs are identical. To illustrate how isomorphism entails the preservation of structural properties while allowing for variations in state representations, we exhaustively explore the isomorphic reversible rules in the first degree CAs (FDCAs), that is, the simple three-neighborhood CAs represented by eight parameters. The experimental study includes reversible FDCAs for states two to 10 with cell lengths of four to seven under the null boundary condition and states two to seven with cell lengths of four to seven under the periodic boundary condition. Given a CA, we also provide two synthesis methods for identifying the set of CAs that are isomorphic to it. The first method operates by permuting the states of a group of CA cell locations, whereas the second method involves exchanging cells at various points. We demonstrate that, depending on the range of exchanged cell positions, the isomorphic CAs produced in this way may have a bigger neighborhood than the input CA. Finally, we provide an exhaustive classification of the elementary CAs (ECAs) using the first synthesis method and compare it with existing results.

Keywords: first degree cellular automaton; FDCA; parameters; reversibility; cycle structure; classification; synthesis schemes

Cite this publication as:
V. Vikrant, K. Bhattacharjee and S. Mukherjee, “Isomorphic Classification of First Degree Cellular Automata,” Complex Systems, 34(1), 2025 pp. 59–90.
https://doi.org/10.25088/ComplexSystems.34.1.59