Tesselations with local transformations

DOI10.1016/S0022-0000(72)80009-6zbMath0246.94037OpenAlexW1985779652WikidataQ55921396 ScholiaQ55921396MaRDI QIDQ2555840

Yanyan Li

Publication date: 1972

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(72)80009-6

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Other designs, configurations (05B30)

Related Items (86)

Cellular automata and strongly irreducible shifts of finite type. ⋮ Invertible shift-invariant transformations on binary arrays ⋮ Group structured linear cellular automata over \(Z_ m\) ⋮ Computability with low-dimensional dynamical systems ⋮ Unnamed Item ⋮ Semi-strongly irreducible shifts ⋮ Efficient exhaustive listings of reversible one dimensional cellular automata ⋮ On the size of the inverse neighborhoods for one-dimensional reversible cellular automata ⋮ Intrinsic universality of a 1-dimensional reversible Cellular Automaton ⋮ Inversion of 2D cellular automata: Some complexity results ⋮ Predecessors of cellular automata states. II: Pre-images of finite sequences ⋮ The surjectivity problem for 2D cellular automata ⋮ A tight linear bound on the synchronization delay of bijective automata ⋮ Dynamical characteristics of linear cellular automata ⋮ Some properties of topological pressure on cellular automata ⋮ Growing patterns in 1D cellular automata ⋮ The topological pressure of linear cellular automata ⋮ Continuous Relations and Richardson’s Theorem ⋮ Intractable problems in reversible cellular automata ⋮ Additive cellular automata and global injectivity ⋮ Ternary reversible number-conserving cellular automata are trivial ⋮ Reversible cellular automaton able to simulate any other reversible one using partitioning automata ⋮ Cellular automata between sofic tree shifts ⋮ Four states are enough! ⋮ On the image set and reversibility of shift morphisms over discrete alphabets ⋮ SHARING SECRETS USING ELEMENTARY CELLULAR AUTOMATA ⋮ An interconnection of local maps inducing onto global maps ⋮ Remarks on permutive cellular automata. ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Inversion of Mutually Orthogonal Cellular Automata ⋮ Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage ⋮ On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View ⋮ Representation of reversible cellular automata with block permutations ⋮ Topological dynamics of nondeterministic cellular automata ⋮ Pattern decomposition for tessellation automata ⋮ Strong surjectivity is equivalent to C-injectivity ⋮ Reversible computing and cellular automata -- a survey ⋮ Induced Subshifts and Cellular Automata ⋮ Structure of the invertible CA transformations group ⋮ The structure of reversible one-dimensional cellular automata ⋮ Hybrid one-dimensional reversible cellular automata are regular ⋮ Firing squad synchronization problem in reversible cellular automata ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ Nondeterministic cellular automata ⋮ Unnamed Item ⋮ Continuity of information transport in surjective cellular automata ⋮ Uniform continuity of relations and nondeterministic cellular automata ⋮ A closed formula for the inverse of a reversible cellular automaton with \((2 R + 1)\)-cyclic rule ⋮ Linear cellular automata on Cayley graphs ⋮ Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata ⋮ Reproduction in tessellation structures ⋮ On reversibility in cellular automata ⋮ Theory of cellular automata: a survey ⋮ MINIMAL FORBIDDEN PATTERNS OF MULTI-DIMENSIONAL SHIFTS ⋮ Computation and construction universality of reversible cellular automata ⋮ Certain relations between properties of maps of tessellation automata ⋮ A note on pattern reproduction in tessellation structures ⋮ Local maps inducing surjective global maps of one-dimensional tessellation automata ⋮ (A-)synchronous (non)-deterministic cell spaces simulating each other ⋮ When-and how-can a cellular automaton be rewritten as a lattice gas? ⋮ Injectivity and surjectivity of parallel maps for cellular automata ⋮ Decidability for some problems of linear cellular automata over finite commutative rings ⋮ Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects ⋮ PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS ⋮ REVERSIBILITY OF A SYMMETRIC LINEAR CELLULAR AUTOMATA ⋮ ON THE REVERSIBILITY OF 150 WOLFRAM CELLULAR AUTOMATA ⋮ Reversibility of non-saturated linear cellular automata on finite triangular grids ⋮ Confusion in the Garden of Eden ⋮ Some applications of propositional logic to cellular automata ⋮ Reversibility of number-conserving 1D cellular automata: unlocking insights into the dynamics for larger state sets ⋮ Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures ⋮ On the induction operation for shift subspaces and cellular automata as presentations of dynamical systems ⋮ A word-counting technique for the solution of stochastic equations ⋮ Graph-theoretical characterization of invertible cellular automata ⋮ Reversible space-time simulation of cellular automata ⋮ Open maps for tessellation automata ⋮ Linear cellular automata over \(Z_ m\) ⋮ Indecomposable maps in tesselation structures of arbitrary dimension ⋮ Inverse and Injectivity of Parallel Relations Induced by Cellular Automata ⋮ Computation in reversible cellular automata ⋮ Computation theoretic aspects of cellular automata ⋮ Cellular automata and discrete neural networks ⋮ Reversibility of 2D cellular automata is undecidable ⋮ Invertible cellular automata: A review ⋮ Reversibility and surjectivity problems of cellular automata ⋮ Randomness on full shift spaces

Cites Work

• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• The Garden-of-Eden Theorem for Finite Configurations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Tesselations with local transformations