9 papers
The Invertibility of Cellular Automata with Menory: Correcting Errors and New Conclusions
Chen Wang, Xiang Deng, Chao Wang
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 con…
Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
Ma Junchi, Chen Weilin, Wang Chen +2
The property of reversibility is quite meaningful for the classic theoretical computer science model, cellular automata. For the reversibility problem for a CA under null boundary…
Efficient Computation for Invertibility Sequence of Banded Toeplitz Matrices
Chen Wang, Chao Wang
When solving systems of banded Toeplitz equations or calculating their inverses, it is necessary to determine the invertibility of the matrices beforehand. In this paper, we equate…
Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
Chen Wang, Chao Wang, Gregory Z. Gutin +1
Let be a graph and let each vertex of has a lamp and a button. Each button can be of -type or -type. Assume that initially some lamps are on and others are o…
Determinants and Inverses of banded Toeplitz Matrices over Are Periodic
Chen Wang, Chao Wang
Banded Toeplitz matrices over , as a well-known class of matrices, have been extensively studied in the fields of coding theory and automata theory. In this paper, we…
Efficient Calculations for Inverse of -diagonal Circulant Matrices and Cyclic Banded Matrices
Chen Wang, Hailong Yu, Chao Wang
-diagonal circulant matrices and cyclic banded matrices are widely used in numerical simulations and signal processing of circular linear systems. Algorithms that directly invol…
Two Graphs: Resolving the Periodic Reversibility of One-dimensional Finite Cellular Automata
Chen Wang, Junchi Ma, Chao Wang +2
Finite cellular automata (FCA) are widely used in simulating nonlinear complex systems, and their reversibility is closely related to information loss during the evolution. However…
Patterns Induce Injectivity: A New Thinking in Constructing Injective Local Rules of 1D Cellular Automata over
Defu Lin, Weilin Chen, Chen Wang +2
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 t…
Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
Chen Wang, Junchi Ma, Defu Lin +2
Nonlinear cellular automata are extensively used in simulations, image processing, cryptography, and so on. The determination of their fundamental properties, injectivity and surje…