Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.05642 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914830058782720 |
|---|---|
| author | Wang, Chen Deng, Xiang Wang, Chao |
| author_facet | Wang, Chen Deng, Xiang Wang, Chao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05642 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Invertibility of Cellular Automata with Menory: Correcting Errors and New Conclusions Wang, Chen Deng, Xiang Wang, Chao Cellular Automata and Lattice Gases Data Structures and Algorithms 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. |
| title | The Invertibility of Cellular Automata with Menory: Correcting Errors and New Conclusions |
| topic | Cellular Automata and Lattice Gases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.05642 |