2023/09/27 by Defu Lin, Lin, Defu, Weilin Chen +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Data Storage Technologies #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Physical sciences
paper · pdf · doi:10.48550/arxiv.2309.15468
openalex publication_date 2023/09/27 · openalex created_date 2023/09/30 · openalex updated_date 2026/07/28
We discovered that certain patterns called injective patterns remain stable during the revolution process, allowing us to create many reversible CA simply by using them to design the revolution rules. By examining injective patterns, we investigated their structural stability during revolutions. This led us to discover extended patterns and pattern mixtures that can create more reversible cellular automata. Furthermore, our research proposed a new way to study the reversibility of CA by observing the structure of local rule f. In this paper, we will explicate our study and propose an efficient method for finding the injective patterns. Our algorithms can find injective rules and generate local rule f by traversing 2N, instead of 2^2N to check all injective rules and pick the injective ones.