Back to Search
Start Over
Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over [formula omitted].
- Source :
-
Information Sciences . May2022, Vol. 594, p163-176. 14p. - Publication Year :
- 2022
-
Abstract
- The property of reversibility is quite meaningful for the classic theoreticabl computer science model, cellular automata. This paper focuses on the reversibility of general one-dimensional (1D) linear cellular automata (LCA), under null boundary conditions over the finite field Z p . Although the existing approaches have split the reversibility challenge into two sub-problems: calculate the period of reversibility first, then verify the reversibility in a period, they are still exponential in the size of the CA's neighborhood. In this paper, we use two efficient algorithms with polynomial complexity to tackle these two challenges, making it possible to solve large-scale reversible LCA, which substantially enlarge its applicability. Finally, we provide an interesting perspective to inversely generate a 1D LCA from a given period of reversibility. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00200255
- Volume :
- 594
- Database :
- Academic Search Index
- Journal :
- Information Sciences
- Publication Type :
- Periodical
- Accession number :
- 155886398
- Full Text :
- https://doi.org/10.1016/j.ins.2022.01.045