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.

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)