Search: onr:"swepub:oai:DiVA.org:kth-321184" >
Efficient methods w...
Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over Zp
-
Du, X. (author)
-
Wang, C. (author)
-
- Wang, Tianze (author)
- KTH,Programvaruteknik och datorsystem, SCS
-
show more...
-
Gao, Z. (author)
-
show less...
-
(creator_code:org_t)
- Elsevier BV, 2022
- 2022
- English.
-
In: Information Sciences. - : Elsevier BV. - 0020-0255 .- 1872-6291. ; 594, s. 163-176
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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 Zp. 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.
Subject headings
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Keyword
- Cellular automata
- Linear rule
- Null boundary
- Polynomial complexity
- Reversibility
- Computational complexity
- Polynomials
- Cellular automatons
- Exponentials
- Finite fields
- One-dimensional
- Property
- Sub-problems
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database