Injectivity and surjectivity of parallel maps for cellular automata

DOI10.1016/0022-0000(79)90051-5zbMath0411.68047OpenAlexW2089823594WikidataQ121832528 ScholiaQ121832528MaRDI QIDQ1259427

Masayuki Kimura, Akira Maruoka

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(79)90051-5

zbMATH Keywords

injectivitycellular automatasurjectivitytwo-dimensional arraysparallel mapneighbourhood index

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items

Predecessors of cellular automata states. II: Pre-images of finite sequences, Asynchronous cellular automata and dynamical properties, A survey of cellular automata: types, dynamics, non-uniformity and applications, Strong surjectivity is equivalent to C-injectivity, Reversible computing and cellular automata -- a survey, Linear cellular automata on Cayley graphs, Some Formal Properties of Asynchronous Cellular Automata, When-and how-can a cellular automaton be rewritten as a lattice gas?, Linear cellular automata over \(Z_ m\), Computation theoretic aspects of cellular automata, Invertible cellular automata: A review, Randomness on full shift spaces

Cites Work

• Unnamed Item
• Completeness problem of one-dimensional binary scope-3 tessellation automata
• Certain relations between properties of maps of tessellation automata
• A completeness problem for pattern generation in tessellation automata
• Tesselations with local transformations
• Condition for injectivity of global maps for tessellation automata
• Inverse and Injectivity of Parallel Relations Induced by Cellular Automata
• Local maps inducing surjective global maps of one-dimensional tessellation automata
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• The Garden-of-Eden Theorem for Finite Configurations