Freezing, Bounded-Change and Convergent Cellular Automata
From MaRDI portal
Publication:5864724
DOI10.46298/dmtcs.5734zbMath1499.68213arXiv1908.06751MaRDI QIDQ5864724
Guillaume Theyssier, Nicolas Ollinger
Publication date: 8 June 2022
Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1908.06751
68Q25: Analysis of algorithms and problem complexity
68Q80: Cellular automata (computational aspects)
Related Items
Building squares with optimal state complexity in restricted active self-assembly, Cold dynamics in cellular automata: a tutorial, The mirage of universality in cellular automata
Cites Work
- An introduction to tile-based self-assembly and a survey of recent results
- On time-symmetry in cellular automata
- Computability and complexity in self-assembly
- Communication complexity and intrinsic universality in cellular automata
- Limitations of self-assembly at temperature 1
- Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems
- Rice's theorem for the limit sets of cellular automata
- Sharp metastability threshold for two-dimensional bootstrap percolation
- Counter machines and distributed automata -- a story about exchanging space and time
- Universality in freezing cellular automata
- On the computational complexity of the freezing non-strict majority automata
- Universality and decidability of number-conserving cellular automata
- Cellular automata with sparse communication
- Rice’s Theorem for μ-Limit Sets of Cellular Automata
- Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue
- A Brief Tour of Theoretical Tile Self-Assembly
- Periodicity and Immortality in Reversible Computing
- P-completeness of Cellular Automaton Rule 110
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Condition for injectivity of global maps for tessellation automata
- Communication Complexity
- Cellular Automata Modeling of Physical Systems
- On Nilpotency and Asymptotic Nilpotency of Cellular Automata
- Endomorphisms and automorphisms of the shift dynamical system
- The undecidability of the domino problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
