2024/06/09 by Chen Wang, Xiang Deng, Wang, Chen +3
Computer Science · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2406.05642
openalex publication_date 2024/06/09 · openalex created_date 2024/06/12 · openalex updated_date 2026/07/28
Cellular automata with memory (CAM) are widely used in fields such as image processing, pattern recognition, simulation, and cryptography. The invertibility of CAM is generally considered to be chaotic. Paper [Invertible behavior in elementary cellular automata with memory, Juan C. Seck-Tuoh-Mora et al., Information Sciences, 2012] presented necessary and sufficient conditions for the invertibility of elementary CAM, but it contains a critical error: it classifies identity CAM as non-invertible, whereas identity CAM is undoubtedly invertible. By integrating Amoroso's algorithm and cycle graphs, we provide the correct necessary and sufficient conditions for the invertibility of one-dimensional CAM. Additionally, we link CAM to a specific type of cellular automaton that is isomorphic to CAM, behaves identically, and has easily determinable invertibility. This makes it a promising alternative tool for CAM applications.