10.46298/dmtcs.2977
https://dmtcs.episciences.org/2977
Briceño, Raimundo
Raimundo
Briceño
Meunier, Pierre-Etienne
Pierre-Etienne
Meunier
The structure of communication problems in cellular automata
Studying cellular automata with methods from communication complexity appears to be a promising approach. In the past, interesting connections between communication complexity and intrinsic universality in cellular automata were shown. One of the last extensions of this theory was its generalization to various "communication problems'', or "questions'' one might ask about the dynamics of cellular automata. In this article, we aim at structuring these problems, and find what makes them interesting for the study of intrinsic universality and quasi-orders induced by simulation relations.
episciences.org
cellular automata
communication complexity
intrinsic universality
ideals
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS]
[NLIN.NLIN-CG] Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG]
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
2023-04-02
2011-01-01
2011-01-01
en
journal article
https://hal.science/hal-01196144v1
1365-8050
https://dmtcs.episciences.org/2977/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems
Proceedings
Researchers
Students