Communication complexity meets cellular automata: necessary conditions for intrinsic universality
From MaRDI portal
Publication:6095497
DOI10.1007/s11047-021-09857-zzbMath1530.68159OpenAlexW3171449992MaRDI QIDQ6095497
Raimundo Briceño, Ivan Rapaport
Publication date: 8 September 2023
Published in: Natural Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11047-021-09857-z
Cellular automata (computational aspects) (68Q80) Communication complexity, information complexity (68Q11)
Cites Work
- The two-handed tile assembly model is not intrinsically universal
- Bulking II: Classifications of cellular automata
- Communication complexity in number-conserving and monotone cellular automata
- Communication complexity and intrinsic universality in cellular automata
- Four states are enough!
- On dissemination thresholds in regular and irregular graph classes
- Invertible cellular automata: A review
- Global fixed point attractors of circular cellular automata and periodic tilings of the plane: Undecidability results
- Reversibility and surjectivity problems of cellular automata
- Theory of cellular automata: a survey
- Cellular automata and communication complexity
- Letting Alice and Bob choose which problem to solve: implications to the study of cellular automata
- Universality results for kinetically constrained spin models in two dimensions
- Solving the density classification problem with a large diffusion and small amplification cellular automaton
- Fully asynchronous behavior of double-quiescent elementary cellular automata
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Deploying Wireless Networks with Beeps
- Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol
- P-completeness of Cellular Automaton Rule 110
- Statistical mechanics of cellular automata
- On Communicating Finite-State Machines
- On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
- Languages, equicontinuity and attractors in cellular automata
- Distributed Computing: A Locality-Sensitive Approach
- Communication Complexity
- Stone age distributed computing
- Computational Complexity
- Intrinsic universality in tile self-assembly requires cooperation
- On Local Symmetries and Universality in Cellular Automata
- Endomorphisms and automorphisms of the shift dynamical system
- Simple Computation-Universal Cellular Spaces
- STACS 2005
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
