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

DOI10.1016/J.TCS.2010.07.011MaRDI QIDQ604472zbMATH OpenOpenAlexFDO

Authors Gianluca Caterina, Bruce M. Boghosian

Publication date 11 November 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0807.3046

zbMATH Keywords

cellular automataconserved quantitiesdiscrete dynamical systemselementary reversible cellular automatainvariantsNoether's theoremreversibility

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

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 $psi(f)subseteqpsi(fveeg)$, where $psi(f)$ denotes the set of additive invariants of $f$ and $subseteq$ denotes the inclusion relation between real subspaces.

Recommendations

• The structure of reversible one-dimensional cellular automata
• Invariant in cellular automata
• Block invariance and reversibility of one dimensional linear cellular automata
• On the structure of the set of reversible cellular automata
• On reversibility of cellular automata with periodic boundary conditions

Cites work

• Additive conserved quantities in discrete-time lattice dynamical systems
• Algebraic properties of cellular automata
• Boltzmann-type equations for elementary reversible cellular automata
• Cellular automaton rules conserving the number of active sites
• Combinatorics of conservation laws.
• Conservation laws in cellular automata
• Conservative logic
• Endomorphisms and automorphisms of the shift dynamical system
• Ergodic properties and thermodynamic behavior of elementary reversible cellular automata. I. Basic properties.
• scientific article; zbMATH DE number 1886322 (Why is no real title available?)
• Invariant in cellular automata
• Reversibility of 2D cellular automata is undecidable
• The Most General Conservation Law for a Cellular Automaton
• Theory of cellular automata: a survey

Cited in

(1)

• scientific article; zbMATH DE number 5190408 (Why is no real title available?)

This page was built for publication: An order-preserving property of additive invariants for Takesue-type reversible cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q604472)