pith. sign in

arxiv: 1907.06012 · v1 · pith:IG7IFF63new · submitted 2019-07-13 · 💻 cs.CC · cs.FL· nlin.CG

Efficient methods to determine the reversibility of general 1D linear cellular automata in polynomial complexity

Xinyu Du , Chao Wang , Tianze Wang , Zeyu Gao This is my paper

Pith reviewed 2026-05-24 22:08 UTC · model grok-4.3

classification 💻 cs.CC cs.FLnlin.CG
keywords linear cellular automatareversibilitypolynomial complexitynull boundary conditionperiod calculationverification algorithmcryptography applications
0
0 comments X

The pith

Two algorithms compute the reversibility period and verify it for any 1D linear cellular automaton under null boundaries in polynomial time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper focuses on determining reversibility for one-dimensional linear cellular automata with null boundary conditions. Prior approaches to finding the reversibility period and then checking reversibility inside that period required too much time and space to scale beyond small sizes. The authors present two new algorithms that handle period calculation and verification efficiently enough to work on very large automata. The same efficiency also supports generating an automaton from a chosen reversibility period. These steps make reversibility analysis practical for applications that need large reversible rules.

Core claim

The reversibility of general 1D linear cellular automata under null boundary conditions is decided by first computing the period of reversibility and then verifying reversibility within that period; both tasks are solved by dedicated polynomial-time algorithms that operate on the matrix or polynomial representation of the transition rule.

What carries the argument

The pair of algorithms that compute the reversibility period and perform verification inside it, using the matrix or polynomial form of an arbitrary linear rule.

If this is right

  • Reversibility of linear automata with thousands of cells becomes computable.
  • An automaton can be constructed directly from any supplied reversibility period.
  • Cryptographic systems that rely on reversible cellular automata can be tested at larger scales.
  • The overall process of checking reversibility no longer becomes intractable once size grows.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same polynomial-time approach may extend to periodic or other boundary conditions if their transition matrices admit similar efficient period extraction.
  • If the algorithms remain polynomial for all rules, reversibility for this class of automata lies in P.
  • Implementations could be used to enumerate large families of reversible rules for experimental study of their dynamics.
  • The generation method opens a design route: pick a period first, then obtain a matching rule.

Load-bearing premise

The matrix or polynomial representations used for arbitrary linear rules permit period computation and verification steps that stay polynomial without hidden exponential costs in the general case.

What would settle it

A concrete linear rule of size n where either algorithm requires more than O(n^k) steps for some fixed k, or where it returns the wrong reversibility verdict on a known example.

Figures

Figures reproduced from arXiv: 1907.06012 by Chao Wang, Tianze Wang, Xinyu Du, Zeyu Gao.

Figure 1
Figure 1. Figure 1: The DFA of linear rule 11001 with the neighbor vector (-2, -1, 0, 1, 2) [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Constructing 0-labelled edge to get the next node [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Translate linear rule to polynomial to calculate the period of the reversibility of LCA [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Use rR tuples to represent 2rR − rR − 1 tuples in the initial node, where rL = rR = 3. Every tuple transformed from the initial node can still be represented by the linear combination of tuples in its current node of index 2j (j = 0, 1, .., rR − 1) with the same coefficients e1, e2...erR as it is represented in the initial node. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Use standard basis postfix to judge reversibility [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
read the original abstract

In this paper, we study reversibility of one-dimensional(1D) linear cellular automata(LCA) under null boundary condition, whose core problems have been divided into two main parts: calculating the period of reversibility and verifying the reversibility in a period. With existing methods, the time and space complexity of these two parts are still too expensive to be employed. So the process soon becomes totally incalculable with a slightly big size, which greatly limits its application. In this paper, we set out to solve these two problems using two efficient algorithms, which make it possible to solve reversible LCA of very large size. Furthermore, we provide an interesting perspective to conversely generate 1D LCA from a given period of reversibility. Due to our methods' efficiency, we can calculate the reversible LCA with large size, which has much potential to enhance security in cryptography system.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper claims to introduce two efficient algorithms for 1D linear cellular automata (LCA) under null boundary conditions: one to compute the reversibility period and one to verify reversibility within that period. These are asserted to run in polynomial time, enabling solutions for very large sizes where prior methods fail due to high time/space complexity. The work also describes a method to generate 1D LCA rules from a prescribed reversibility period, with suggested applications to cryptography.

Significance. If the polynomial-time bounds hold without hidden exponential dependence on the group order or polynomial degree, the algorithms would enable practical reversibility analysis and rule generation for large n, addressing a clear computational bottleneck in the field and potentially supporting cryptographic constructions that rely on reversible LCA.

major comments (1)
  1. [Abstract] Abstract and central claims: the assertion that the two new algorithms achieve polynomial time for arbitrary linear rules (including period computation) is presented without any derivation, complexity proof, pseudocode, or reduction showing that the multiplicative order of the transition matrix (or equivalent polynomial representation) can be computed without exponential factors in the general case. Verification of invertibility is polynomial via standard linear algebra, but the period step is not shown to be.

Simulated Author's Rebuttal

1 responses · 0 unresolved

Thank you for the review and the recommendation for major revision. We address the concern about the lack of derivation and proof for the polynomial-time claim on period computation. We agree the manuscript requires expansion on this point and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract and central claims: the assertion that the two new algorithms achieve polynomial time for arbitrary linear rules (including period computation) is presented without any derivation, complexity proof, pseudocode, or reduction showing that the multiplicative order of the transition matrix (or equivalent polynomial representation) can be computed without exponential factors in the general case. Verification of invertibility is polynomial via standard linear algebra, but the period step is not shown to be.

    Authors: We agree that the current version presents the algorithms at a high level without sufficient derivation, pseudocode, or explicit complexity analysis for computing the reversibility period (i.e., the multiplicative order of the transition matrix or its polynomial equivalent). Invertibility verification is handled via standard linear algebra over the ring, which is polynomial. For the period, the manuscript relies on the structure of 1D null-boundary LCA to reduce the problem to operations on degree-n polynomials, but does not detail how the order is extracted in polynomial time without exponential factors in n or the group order. In the revision we will add a dedicated section with pseudocode for both algorithms and a proof that the order computation reduces to repeated squaring and gcd operations on polynomials of degree O(n) over a finite ring (with bit complexity polynomial in n and the bit length of the rule coefficients), confirming no hidden exponential dependence. This substantiates the central claim. revision: yes

Circularity Check

0 steps flagged

No circularity; algorithmic claims do not reduce to self-defined quantities or self-citations

full rationale

The abstract and provided text describe two new algorithms for period calculation and reversibility verification of 1D LCA but contain no equations, fitted parameters, or derivations. No self-citation chains, ansatzes smuggled via prior work, or renamings of known results are present. The polynomial-time claim is an assertion about algorithmic complexity rather than a derivation that collapses to its inputs by construction. Per the rules, absence of quotable reductions means score 0 with empty steps list.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated.

pith-pipeline@v0.9.0 · 5692 in / 1096 out tokens · 22712 ms · 2026-05-24T22:08:48.903824+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 1 internal anchor

  1. [1]

    H. Akin, F. Sah and I. Siap, On 1D Reversible Cellular Automata with Reflective Boundary Over the Prime Field of Order p, Int. J. Mod. Phys. C, 23(1)(2012) 1250004:1-13. 23

    work page 2012

  2. [2]

    Berlekamp, Factoring polynomials over finite fields, Bell System Technical Journal, 46(8)(1967) 1853-1859

    E. Berlekamp, Factoring polynomials over finite fields, Bell System Technical Journal, 46(8)(1967) 1853-1859

    work page 1967

  3. [3]

    Bakhshandeh and Z

    A. Bakhshandeh and Z. Eslami, An authenticated image encryption scheme based on chaotic maps and memory cellular automata, Optics and Lasers in Engineering, 51(6)(2013) 665-673

    work page 2013

  4. [4]

    Berlekamp, Algebraic coding theory, World Scientific, New Jersey, 2015

    E. Berlekamp, Algebraic coding theory, World Scientific, New Jersey, 2015

    work page 2015

  5. [5]

    D. G. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Mathe- matics of Computation, (1981) 587-592

    work page 1981

  6. [6]

    Chang, J

    C. Chang, J. Su, etc., Reversibility of linear cellular automata on Cayley trees with periodic boundary condition, Taiwanese Journal of Mathematics, 21(6)(2017) 1335-1353

    work page 2017

  7. [7]

    Chang, J

    C. Chang, J. Su, H. Akın and F. S ¸ah, Reversibility Problem of Multidimensional Finite Cellular Automata, Journal of Statistical Physics, 168(1)(2017) 208-231

    work page 2017

  8. [8]

    Cinkir, A

    Z. Cinkir, A. Hasan and I. Siap, Reversibility of 1D Cellular Automata with Periodic Boundary over Finite Fields Z(p), J. Stat. Phys., 143(4)(2011) 807-823

    work page 2011

  9. [9]

    A Parallel Encryption Algorithm for Block Ciphers Based on Reversible Programmable Cellular Automata

    D. Das and A. Ray, A parallel encryption algorithm for block ciphers based on reversible programmable cellular automata, arXiv:1006.2822, 2010

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  10. [10]

    A. M. del Rey and G. Rodr´ ıguez S´ anchez, On the reversibility of 150 Wolfram cellular automata, Int. J. Mod. Phys. C, 17(7)(2006) 975-983

    work page 2006

  11. [11]

    A. M. del Rey and G. Rodr´ ıguez S´ anchez, Reversibility of a Symmetric Linear Cellular Automata, Int. J. Mod. Phys. C, 20(7)(2009) 1081-1086

    work page 2009

  12. [12]

    A. M. del Rey and G. Rodr´ ıguez S´ anchez, Reversibility of linear cellular automata, Appl. Math. Comput., 217(21)(2011) 8360-8366

    work page 2011

  13. [13]

    A. M. del Rey, A Note on the Reversibility Of Elementary Cellular Automaton 150 With Periodic Boundary Conditions, Rom. J. Inf. Sci. Tech., 16(4)(2013) 365-372

    work page 2013

  14. [14]

    A. M. del Rey and G. Rodr´ ıguez S´ anchez, On the invertible cellular automata 150 over Fp, Appl. Math. Comput., 219(10)(2013) 5427-5432

    work page 2013

  15. [15]

    Hern´ andez Encinas and A

    L. Hern´ andez Encinas and A. Mart´ ın del Rey, Inverse rules of ECA with rule number 150, Appl. Math. Comput., 189(2)(2007) 1782-1786

    work page 2007

  16. [16]

    Kari, Reversibility of 2D cellular automata is undecidable, Physica D, 45(1-3)(1990) 379-385

    J. Kari, Reversibility of 2D cellular automata is undecidable, Physica D, 45(1-3)(1990) 379-385

    work page 1990

  17. [17]

    Kari, Cryptosystems based on reversible cellular automata, Manuscript, 1992

    J. Kari, Cryptosystems based on reversible cellular automata, Manuscript, 1992. 24

    work page 1992

  18. [18]

    Kippenberger, A

    S. Kippenberger, A. Bernd, D. Tha¸ ci, etc., Modeling pattern formation in skin diseases by a cellular automaton, The Journal of investigative dermatology, 133(2)(2013) 567

    work page 2013

  19. [19]

    G. ´A. Mara˜ n´ on, L. H. Encinas and A. M. del Rey, A new secret sharing scheme for images based on additive 2-dimensional cellular automata, Iberian Conference on Pattern Recognition and Image Analysis, 2005, 411-418

    work page 2005

  20. [20]

    R. W. Marsh, Table of irreducible polynomials over GF(2) through degree 19, Office of Technical Services, US Department of Commerce, 1957

    work page 1957

  21. [21]

    Nobe and F

    A. Nobe and F. Yura, On reversibility of cellular automata with periodic boundary conditions, J. Phys. A-Math. Gen., 37(22)(2004) 5789-5804

    work page 2004

  22. [22]

    Rickert, K

    M. Rickert, K. Nagel, M. Schreckenberg and A. Latour, Two lane traffic simulations using cellular automata, Physica A: Statistical Mechanics and its Applications, 231(4)(1996) 534-550

    work page 1996

  23. [23]

    F. Sah, I. Siap and H. Akin, Characterization of Three Dimensional Cellular Automata over Z(m), AIP Conference Proceedings, 1470, Aug.2012, 138-141

    work page 2012

  24. [24]

    Palash Sarkar and Rana Barua, The set of reversible 90 /150 cellular automata is regular, Discret. Appl. Math., 84(1-3)(1998) 199-213

    work page 1998

  25. [25]

    J. C. Seck-Tuoh-Mora, G. J. Martinez, R. Alonso-Sanz and N. Hernandez-Romero, Invertible behavior in elementary cellular automata with memory, Inf. Sci., 199(1)(2012) 125-132

    work page 2012

  26. [26]

    J. C. Seck-Tuoh-Mora, J. Medina-Marin, N. Hernandez-Romero, etc., Invertible behavior in elementary cellular automata with memory, Inf. Sci., 382(1)(2017) 81-95

    work page 2017

  27. [27]

    J. C. Seck-Tuoh-Mora and G. J. Mart´ ınez, Graphs Related to Reversibility and Complexity in Cellular Automata, Cellular Automata: A Volume in the Encyclopedia of Complexity and Systems Science, Second Edition, Springer, 2018, 479-492

    work page 2018

  28. [28]

    Shoup, New algorithms for finding irreducible polynomials over finite fields, Mathematics of Com- putation, 54(189)(1990) 435-447

    V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Mathematics of Com- putation, 54(189)(1990) 435-447

    work page 1990

  29. [29]

    I. Siap, H. Akin and F. Sah, Garden of eden configurations for 2-D cellular automata with rule 2460 N, Inf. Sci., 180(18)(2010) 3562-3571

    work page 2010

  30. [30]

    I. Siap, H. Akin and S. U˘ guz, Structure and reversibility of 2D hexagonal cellular automata, Comput. Math. Appl., 62(11)(2011) 4161-4169

    work page 2011

  31. [31]

    I. Siap, H. Akin and M. E. Koroglu, Reversible Cellular Automata with Penta-Cyclic Rule and ECCs, Int. J. Mod. Phys. C, 23(10)(2012) 50066:1-13. 25

    work page 2012

  32. [32]

    Souyah and K

    A. Souyah and K. M. Faraoun, Fast and efficient randomized encryption scheme for digital images based on quadtree decomposition and reversible memory cellular automata, Nonlinear Dynamics, 84(2)(2016) 715-732

    work page 2016

  33. [33]

    Sutner, sigma-automata and Chebyshev-polynomials, Theor

    K. Sutner, sigma-automata and Chebyshev-polynomials, Theor. Comput. Sci., 230(1-2)(2000) 49-73

    work page 2000

  34. [34]

    Takesue, Ergodic properties and thermodynamic behavior of elementary reversible cellular automata

    S. Takesue, Ergodic properties and thermodynamic behavior of elementary reversible cellular automata. I. Basic properties, Journal of Statistical Physics, 56(3-4)(1989) 371-402

    work page 1989

  35. [35]

    U˘ guz, H

    S. U˘ guz, H. Akin and I. Siap, Reversibility Algorithms for 3-State Hexagonal Cellular Automata with Periodic Boundaries, Int. J. Bifurcat. Chaos, 23(6)(2013) 1350101: 1-15

    work page 2013

  36. [36]

    Von Zur Gathen and D

    J. Von Zur Gathen and D. Panario, Factoring polynomials over finite fields: A survey, Journal of Symbolic Computation, 31(1-2)(2001) 3-17

    work page 2001

  37. [37]

    Wang and D

    X. Wang and D. Luan, A novel image encryption algorithm using chaos and reversible cellular au- tomata, Communications in Nonlinear Science and Numerical Simulation, 18(11)(2013) 3075-3085

    work page 2013

  38. [38]

    Wolfram, Cellular automata and complexity: collected papers, CRC Press, 2018

    S. Wolfram, Cellular automata and complexity: collected papers, CRC Press, 2018

    work page 2018

  39. [39]

    Yamagishi, Elliptic curves over finite fields and reversibility of additive cellular automata on square grids, Finite Fields Th

    M. Yamagishi, Elliptic curves over finite fields and reversibility of additive cellular automata on square grids, Finite Fields Th. App., 19(1)(2013) 105-119

    work page 2013

  40. [40]

    B. Yang, C. Wang and A. Xiang, Reversibility of general 1D linear cellular automata over the binary field Z2 under null boundary conditions, Information Sciences, 324(1)(2015) 23-31

    work page 2015

  41. [41]

    Zhang, Q

    C. Zhang, Q. Peng and Y. Li, Encryption based on reversible cellular automata, IEEE 2002 Inter- national Conference on Communications, Circuits and Systems and West Sino Expositions, 2(2002), 1223-1226. 26

    work page 2002