An order-preserving property of additive invariant for Takesue-type reversible cellular automata

2008/07/18 by Gianluca Caterina, Bruce M. Boghosian, Caterina, Gianluca +1
Computer Science · Physics and Astronomy · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Computability, Logic, AI Algorithms #FOS: Physical sciences #nlin.CG #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0807.3046

11 pages

arxiv created 2008/07/18 · openalex publication_date 2008/07/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that, for a fairly large class of reversible, one-dimensional cellular automata, the set of additive invariants exhibits an algebraic structure. More precisely, if f and g are one-dimensional, reversible cellular automata of the kind considered by Takesue, we show that there is a binary operation on these automata \vee such that ψ(f)⊆ ψ(f\vee g), where ψ(f) denotes the set of additive invariants of f and ⊆ denotes the inclusion relation between real subspaces.

Citations

• A "No-Go" Theorem for the Existence of an Action Principle for Discrete Invertible Dynamical Systems
• Number-conserving cellular automaton rules

Related

• Second order additive invariants in elementary cellular automata
• Towards a Noether-like conservation law theorem for one dimensional reversible cellular automata
• An Easily Checkable Algebraic Characterization of Positive Expansivity for Additive Cellular Automata over a Finite Abelian Group
• On Finite 1-Dimensional Cellular Automata: Reversibility and Semi-reversibility
• Irreducible Rules and Equivalence Classes of One-dimensional Cellular Automata