The constructibility of a configuration in a cellular automaton

DOI10.1016/S0022-0000(73)80004-2MaRDI QIDQ758953zbMATH OpenFDO

Authors Takeo Yaku

Publication date 1973

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

Full work available at URL https://doi.org/10.1016/S0022-0000(73)80004-2

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Cites work

• A completeness problem for pattern generation in tessellation automata
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• scientific article; zbMATH DE number 3205673 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• scientific article; zbMATH DE number 3338162 (Why is no real title available?)
• Pattern reproduction in tessellation automata of arbitrary dimension
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• Simple Computation-Universal Cellular Spaces
• Some clarifications of the concept of a Garden-of-Eden configuration
• Some regular state sets in the system of one-dimensional iterative automata
• Structural and behavioral equivalences of tessellation automata
• Tessellation structures for reproduction of arbitrary patterns
• The Garden-of-Eden Theorem for Finite Configurations

Cited in

(14)

• Computation theory of cellular automata
• Strong surjectivity is equivalent to C-injectivity
• Survey of research in the theory of homogeneous structures and their applications
• The behavioral properties of homogeneous structures
• Surjectivity of nondeterministic parallel maps induced by nondeterministic cellular automata
• (A-)synchronous (non)-deterministic cell spaces simulating each other
• Computations on nondeterministic cellular automata
• Nonconstructible blocks in 1D cellular automata: minimal generators and natural systems
• On ergodic one-dimensional cellular automata
• Recursive paths in cross-connected trees and an application to cell spaces
• Inverse and Injectivity of Parallel Relations Induced by Cellular Automata
• Two-dimensional cellular automata
• Classifying circular cellular automata
• The general \(\sigma \) all-ones problem for trees

This page was built for publication: The constructibility of a configuration in a cellular automaton

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