Communication complexity and intrinsic universality in cellular automata

DOI10.1016/J.TCS.2010.10.005zbMATH Open1207.68213OpenAlexW1993589452MaRDI QIDQ616488FDOQ616488

Pierre Meunier, Eric Goles, Ivan Rapaport, 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

Recommendations

• scientific article
• Intrinsically universal cellular automata
• Letting Alice and Bob choose which problem to solve: implications to the study of cellular automata
• Efficient unidimensional universal cellular automaton
• scientific article; zbMATH DE number 1962850

zbMATH Keywords

cellular automataintrinsic universalitycommunication complexity

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Cites Work

• Endomorphisms and automorphisms of the shift dynamical system
• Title not available (Why is that?)
• Languages, equicontinuity and attractors in cellular automata
• Directional dynamics for cellular automata: A sensitivity to initial condition approach
• Communication Complexity
• On Local Symmetries and Universality in Cellular Automata
• P-completeness of Cellular Automaton Rule 110
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (19)

• The two-handed tile assembly model is not intrinsically universal
• A Brief Tour of Theoretical Tile Self-Assembly
• Traced communication complexity of cellular automata
• Communication complexity in number-conserving and monotone cellular automata
• Asynchronous communicating cellular automata: formalization, robustness and equivalence
• Unraveling simplicity in elementary cellular automata
• Communication complexity meets cellular automata: necessary conditions for intrinsic universality
• On the complexity of two-dimensional signed majority cellular automata
• The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems
• Building squares with optimal state complexity in restricted active self-assembly
• Title not available (Why is that?)
• Cellular automata with sparse communication
• Freezing, Bounded-Change and Convergent Cellular Automata
• The mirage of universality in cellular automata
• Title not available (Why is that?)
• Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol
• Emergence of universal global behavior from reversible local transitions in asynchronous systems
• Title not available (Why is that?)
• Simulation limitations of affine cellular automata

This page was built for publication: Communication complexity and intrinsic universality in cellular automata

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