The Computation for Reversibility of Arbitrary One-dimensional Finite Cellular Automata Becomes Efficient
Preprint
Abstract
In this paper, we completely solve the reversibility of one-dimensional finite cellular automata (FCA). This means that we will have an efficient method to determine the reversibility of any FCA with all numbers (n) of cells. The complexity of this algorithm is independent of n. We perform calculations on two new kinds of graphs and discover that the reversibility of any FCA exhibits periodicity as n increases. We successfully provide a method to compute the reversibility sequence that encompasses the reversibility of FCA with any number of cells. Additionally, the calculations in this paper are applicable to FCA with various types of boundaries.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata overInformation Sciences, 2022
- Reversibility of number-conserving 1D cellular automata: Unlocking insights into the dynamics for larger state setsPhysica D: Nonlinear Phenomena, 2022
- Efficient enumeration of three-state two-dimensional number-conserving cellular automataInformation and Computation, 2020
- Ternary reversible number-conserving cellular automata are trivialInformation Sciences, 2020
- Reversibility of general 1D linear cellular automata over the binary fieldunder null boundary conditionsInformation Sciences, 2015
- Reversibility of linear cellular automataApplied Mathematics and Computation, 2011
- Reversibility and surjectivity problems of cellular automataJournal of Computer and System Sciences, 1994
- Reversibility of 2D cellular automata is undecidablePhysica D: Nonlinear Phenomena, 1990
- Invertible cellular automata: A reviewPhysica D: Nonlinear Phenomena, 1990
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structuresJournal of Computer and System Sciences, 1972