Reversibility problem of multidimensional finite cellular automata
From MaRDI portal
Publication:2410073
Abstract: While the reversibility of multidimensional cellular automata is undecidable and there exists a criterion for determining if a multidimensional linear cellular automaton is reversible, there are only a few results about the reversibility problem of multidimensional linear cellular automata under boundary conditions. This work proposes a criterion for testing the reversibility of a multidimensional linear cellular automaton under null boundary condition and an algorithm for the computation of its reverse, if it exists. The investigation of the dynamical behavior of a multidimensional linear cellular automaton under null boundary condition is equivalent to elucidating the properties of block Toeplitz matrix. The proposed criterion significantly reduce the computational cost whenever the number of cells or the dimension is large; the discussion can also apply to cellular automata under periodic boundary condition with a minor modification.
Recommendations
- Reversibility of 2D cellular automata is undecidable
- Reversibility of linear cellular automata on Cayley trees with periodic boundary condition
- Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions
- Reversibility of non-saturated linear cellular automata on finite triangular grids
- Reversibility of linear cellular automata
Cites work
- A cryptosystem based on elementary cellular automata
- Block Toeplitz matrices: asymptotic results and applications
- Computation and construction universality of reversible cellular automata
- Computation in reversible cellular automata
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Elliptic curves over finite fields and reversibility of additive cellular automata on square grids
- Field Theory
- Finite fields and applications
- scientific article; zbMATH DE number 4067100 (Why is no real title available?)
- scientific article; zbMATH DE number 635657 (Why is no real title available?)
- Inverse rules of ECA with rule number 150
- Invertible behavior in elementary cellular automata with memory
- Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects
- Irreversibility and Heat Generation in the Computing Process
- Linear cellular automata over \(Z_ m\)
- Logical Reversibility of Computation
- Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
- On reversibility of cellular automata with periodic boundary conditions
- On the Bernoulli automorphism of reversible linear cellular automata
- Resolution Scalable Image Coding With Reversible Cellular Automata
- Reversibility and surjectivity problems of cellular automata
- Reversibility of 1D cellular automata with periodic boundary over finite fields \({\mathbb{Z}}_{p}\)
- Reversibility of 2D cellular automata is undecidable
- Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions
- Reversibility of linear cellular automata
- The dynamics of expansive invertible onesided cellular automata
- The reversibility problem for a family of two-dimensional cellular automata
- Theory of cellular automata: a survey
- Three-state von Neumann cellular automata and pattern generation
- Toeplitz and circulant matrices: a review.
Cited in
(7)- Reversibility of linear cellular automata on Cayley trees with periodic boundary condition
- Generalized reversibility of topological dynamical systems and cellular automata
- The entropy and reversibility of cellular automata on Cayley tree
- scientific article; zbMATH DE number 7179993 (Why is no real title available?)
- Reversibility of linear cellular automata
- Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over \(\mathbb{Z}_p\)
- Reversibility of 2D cellular automata is undecidable
This page was built for publication: Reversibility problem of multidimensional finite cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2410073)
