Structural Properties of Non-Linear Cellular Automata: Permutivity, Surjectivity and Reversibility

Firas Ben Ramdhane, Alberto Dennunzio, Luciano Margara, Giuliamaria Menara · 2025

Read Structural Properties of Non-Linear Cellular Automata: Permutivity, Surjectivity and Reversibility by Firas Ben Ramdhane, Alberto Dennunzio, Luciano Margara, Giuliamaria Menara (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15949.txt.

Introduction

Firas Ben Ramdhane and three co-authors map the rules that make non-linear cell grids act in clean ways. In such a grid, one local rule is used at each cell, all at once. Three traits shape much of what the grid can do. Does each state have a prior state? Can the rule run in reverse? Does it permute in each axis?

The paper shows how these traits — surjectivity, reversibility, and permutivity — push on and bound each other. It gives tests for when a rule is permutive in one sense or in both. Worked cases show where each claim holds and where it stops. Non-linear rules lack the neat tools that settle such points for linear rules. The authors fill that gap. They make clear which acts non-linear grids can and cannot do.

Catalog record

CREATORFiras Ben Ramdhane, Alberto Dennunzio, Luciano Margara, Giuliamaria Menara
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15949

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Structural Properties of Non-Linear Cellular Automata: Permutivity, Surjectivity and Reversibility Firas Ben Ramdhane, Alberto Dennunzio, Luciano Margara, Giuliamaria Menara Abstract This paper explores the algebraic conditions under which a cellular automaton with a non-linear local rule exhibits surjectivity and reversibility. We also analyze the role of permutivity as a key factor influencing these properties and provide conditions that determine whether a non-linear CA is (bi)permutive. Through theoretical results and illustrative examples, we characterize the relationships between these fundamental properties, offering new insights into the dynamical behavior of non-linear CA. 1 Introduction A cellular automaton (CA) is a discrete dynamical system in which each cell updates its state according to local rules, allowing complex global behavior to emerge from simple interactions. CA have been widely employed to model intricate phenomena across diverse scientific fields, including physics [ Den88 ] , biology [ EEK93 ] , sociology [ Heg96 ] , and ecology [ Hog88 ] . Their conceptual simplicity and modeling flexibility have also attracted considerable interest in computer science, particularly in the domain of cryptography (see [ MMM25 ] for a comprehensive survey of cryptographic applications). Among the different classes of CA, linear [ DFGM20a , DFGM21 , DFM24 ] and additive [ Den24 , DFGM20b ] CA have received considerable attention due to their well-understood algebraic structure and predictable behavior. In contrast, non-linear CA remain much less explored, although some attempts have been made to study both qualitatively and quantitatively the characteristics of such CA [ Lan90 , Wue94 , Wue99 ] ): this lack of characterization presents both a challenge and an opportunity. From a theoretical perspective, studying non-linear CA is compelling, as their non-linearity introduces a level of dynamical complexity not present in their linear counterparts. This complexity opens new avenues for analysis and classification, and may reveal behaviors that are fundamentally different from those observed in well-studied classes. In addition, this complexity and unpredictability make non-linear CA promising candidates for applications where such properties are desirable - most notably in cryptography: while linear CA have already been employed in the construction of various cryptographic primitives, the potential of non-linear CA in this domain remains largely untapped. The goal of this paper is to take a step toward bridging this gap by initiating a deeper theoretical study of non-linear CA, starting from classical results addressing the injectivity and surjectivity questions. It is widely acknowledged that characterizing local rules which make a CA injective or surjective proves arduous in the unrestricted case [ Kar00 ] therefore, given the complexity of the issue at hand, we limit our analysis to the class of non-linear j -separated CA, i.e. CA with diameter d and local rule f defined as: f(x_{1},\dots,x_{d+1})=a_{j}x_{j}^{q_{j}}+\pi(x_{1},\dots,x_{j-1},x_{j+1},\dots,x_{d+1}), where a_{j}\in\mathbb{Z}_{m}^{*} , q_{j} is a non negative integer, and \pi:\mathbb{Z}_{m}^{d}\to\mathbb{Z}_{m} is any map (for more details see Definition 1 ). Exploiting the structural properties of j -separated CA, we are able to provide a permutivity characterization in Lemma 3 and Proposition 1 . Then, building on these results and restricting to the class of LR -separated CA, where the local rule f can be written, for 1\leq\ell\leq r\leq d+1 , as f(x_{1},\dots,x_{d+1})=a_{\ell}x_{\ell}^{q_{\ell}}+\pi(x_{\ell+1},\dots,x_{r-1})+a_{r}x_{r}^{q_{r}}, we prove first in Theorem 5.2 that a LR -separated F is surjective if and only if it is either \ell -permutive or r -permutive, and then in Theorem 6.1 that F is reversible if and only if it is reversible shift-like. {theorem*} [cf. Theorems 5.2 and 6.1 ] Let F be a LR -separated CA over the finite ring \mathbb{Z}_{m} , for any integer m\geq 3 , and let \ell (resp. r) be the leftmost (resp. rightmost) positions of F . Then: 1. F is surjective if and only if \gcd(q_{\ell},\varphi(m))=1 or \gcd(q_{r},\varphi(m))=1 . 2. F is injective if and only if \ell=r and \gcd(q_{\ell},\varphi(m))=1 . Besides theoretical results, we also provide illustrative examples to better clarify the relationships between these fundamental properties, offering new insights into the dynamical behavior of non-linear CA. Outline The paper is organized as follows. In Section 2 we recall some relevant algebraic background and notions about the dynamical properties of CA, and we introduce the class of j -separated non-linear CA, which will be essential in the remainder of this work. Further, in Section 4 we proceed by exhibiting algebraic conditions for the local rule f under which the CA is leftmost (or rightmost) permutive. Finally, in Sections 5 and 6 we present the core results of the paper, providing characterization theorems for surjective and reversible j -separated CA. 2 Terminology and Background In this section, we give the preliminary definitions and results needed for the rest of the paper. For a comprehensive introduction on the theory of CA see [ BKR12 , Section 1] and [ Kur03 , Chapter 5] . We start with some terminology from word combinatorics. An alphabet A is a finite set of symbols, called letters . In this paper, we take A=\mathbb{Z}_{m} , the set of integers modulo m . A finite word over an alphabet A is a finite sequence of letters from A . The length of a finite word u , denoted by |u| , is the number of letters it contains. The unique word of length 0 is called the empty word and is denoted by \lambda . A configuration (or bi-infinite word ) x=\ldots x_{-2}x_{-1}x_{0}x_{1}x_{2}\ldots over A is an infinite concatenation of letters from A indexed by \mathbb{Z} . For integers n\leq m , we denote by x_{\left\llbracket n,m\right\rrbracket}=x_{n}x_{n+1}\cdots x_{m-1}x_{m} the subword of x from position n to m , where \left\llbracket n,m\right\rrbracket=[n,m]\cap\mathbb{Z} ; further, we will indicate by u^{\infty} the constant word , i.e. the word constructed by concatenating the same letter u infinitely many times. The set of all finite (resp. bi-infinite) words over A is denoted by A^{*} (resp. A^{\mathbb{Z}} ), and for each n\in\mathbb{N} , the set of words of length n is denoted by A^{n} . Most classically, the set A^{\mathbb{Z}} is endowed with the product topology of the discrete topology on each copy of A . The topology defined on A^{\mathbb{Z}} is metrizable, corresponding to the Cantor distance defined as follows: \mathfrak{d}_{C}(x,y)=2^{-\min\left\{\left.|n|\vphantom{x_{n}\neq y_{n},~n\in\mathbb{Z}}\right|x_{n}\neq y_{n},~n\in\mathbb{Z}\right\}},\forall x\neq y\in A^{\mathbb{Z}},\text{ and }\mathfrak{d}_{C}(x,x)=0,\forall x\in A^{\mathbb{Z}}. This space, called the Cantor space, is compact, totally disconnected and perfect. This topological framework naturally leads to the definition of a topological dynamical system , which provides a formal setting for studying the evolution of configurations under continuous transformations. Recall that a topological dynamical system is a pair (X_{d},F) , where X_{d}=(X,d) is a compact metric space and F\colon X\to X is a continuous map. When X consists of symbolic configurations, such as elements of A^{\mathbb{Z}} , the system is called a symbolic dynamical system . CA are a classical example of such systems. Formally, a CA is a map F\colon A^{\mathbb{Z}}\to A^{\mathbb{Z}} such that there exist an integer \rho\geq 0 and a local rule f\colon A^{2\rho+1}\to A satisfying, for all x\in A^{\mathbb{Z}} and i\in\mathbb{Z}: F(x)_{i}=f(x_{\left\llbracket i-\rho,i+\rho\right\rrbracket}). We refer to \rho as the radius and d=2\rho as the diameter of the CA. A fundamental example of a CA is the shift map , defined on A^{\mathbb{Z}} by \sigma(x)_{i}=x_{i+1} for all i\in\mathbb{Z} . This map plays a central role in the theory

Read the complete text