Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over Zp

• 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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Nyckelord

Cellular automata

Linear rule

Null boundary

Polynomial complexity

Reversibility

Computational complexity

Polynomials

Cellular automatons

Exponentials

Finite fields

One-dimensional

Property

Sub-problems

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)