2026/03/05 by Baby C. J., Kamalika Bhattacharjee · 1 voice
Computer Science · #cs.DM #cs.FL
paper · pdf · doi:10.48550/arxiv.2603.05253
There exists algorithms to detect reversibility of cellular automaton (CA) for both finite and infinite lattices taking quadratic time. But, can we identify a d-state CA rule in constant time that is always reversible for every lattice size n∈ ℕ? To address this issue, this paper explores the reversibility properties of a subset of one-dimensional, 3-neighborhood, d-state finite cellular automata (CAs), known as the first degree cellular automata (FDCAs) for any number of cells (n∈ ℕ) under the null boundary condition. In a first degree cellular automaton (FDCA), the local rule is defined using eight parameters. To ensure that the global transition function of d-state FDCA is reversible for any number of cells (n∈ ℕ), it is necessary and sufficient to verify only three algebraic conditions among the parameter values. Based on these conditions, for any given d, one can synthesize all reversible FDCAs rules. Similarly, given a FDCA rule, one can check these conditions to decide its reversibility in constant time.