Graph-theoretical characterization of invertible cellular automata

DOI10.1016/S0167-2789(00)00020-8zbMath0970.68111WikidataQ56621452 ScholiaQ56621452MaRDI QIDQ1581757

Hendrik Moraal

Publication date: 8 October 2000

Published in: Physica D (Search for Journal in Brave)

zbMATH Keywords

invertible cellular automata

Mathematics Subject Classification ID

Topological dynamics (37B99) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Partial Reversibility of One-Dimensional Cellular Automata, UNCONVENTIONAL INVERTIBLE BEHAVIORS IN REVERSIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA, A survey of cellular automata: types, dynamics, non-uniformity and applications, Highly symmetric cellular automata and their symmetry-breaking patterns, Procedures for calculating reversible one-dimensional cellular automata, A word-counting technique for the solution of stochastic equations

Uses Software

• avida

Cites Work

• Two-dimensional cellular automata
• Predecessors of cellular automata states. I: Additive automata
• Classical, discrete spin models: Symmetry, duality and renormalization
• Computation theoretic aspects of cellular automata
• Reversibility of 2D cellular automata is undecidable
• Invertible cellular automata: A review
• Quasilinear cellular automata
• Computation theory of cellular automata
• Decidability for some problems of linear cellular automata over finite commutative rings
• Predecessors of cellular automata states. II: Pre-images of finite sequences
• Predecessors of cellular automata states. III: Garden of Eden classification of cellular automata
• Additive cellular automata and global injectivity
• Predicting nonlinear cellular automata quickly by decomposing them into linear ones
• Tesselations with local transformations
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Local maps inducing surjective global maps of one-dimensional tessellation automata
• Partially permutive cellular automata
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• Endliche Gruppen I
• Simple Computation-Universal Cellular Spaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item