Communication complexity and intrinsic universality in cellular automata
From MaRDI portal
Publication:616488
DOI10.1016/j.tcs.2010.10.005zbMath1207.68213OpenAlexW1993589452MaRDI QIDQ616488
Pierre-Étienne Meunier, Ivan Rapaport, Eric Goles Chacc, Guillaume Theyssier
Publication date: 10 January 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.005
Related Items
Unraveling simplicity in elementary cellular automata, A Brief Tour of Theoretical Tile Self-Assembly, On the complexity of two-dimensional signed majority cellular automata, The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems, Communication complexity meets cellular automata: necessary conditions for intrinsic universality, Building squares with optimal state complexity in restricted active self-assembly, Asynchronous communicating cellular automata: formalization, robustness and equivalence, Unnamed Item, Unnamed Item, Emergence of universal global behavior from reversible local transitions in asynchronous systems, Traced communication complexity of cellular automata, Communication complexity in number-conserving and monotone cellular automata, The mirage of universality in cellular automata, Freezing, Bounded-Change and Convergent Cellular Automata, The two-handed tile assembly model is not intrinsically universal
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Directional dynamics for cellular automata: A sensitivity to initial condition approach
- Inducing an order on cellular automata by a grouping operation
- Cellular automata and communication complexity
- Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol
- P-completeness of Cellular Automaton Rule 110
- Languages, equicontinuity and attractors in cellular automata
- Communication Complexity
- On Local Symmetries and Universality in Cellular Automata
- Endomorphisms and automorphisms of the shift dynamical system
