Raimundo Briceño ; Pierre-Etienne Meunier - The structure of communication problems in cellular automata

dmtcs:2977 - Discrete Mathematics & Theoretical Computer Science, January 1, 2011, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems - https://doi.org/10.46298/dmtcs.2977
The structure of communication problems in cellular automata

Authors: Raimundo Briceño 1; Pierre-Etienne Meunier 2,2

  • 1 Departamento de Ingeniería Matemática [Santiago]
  • 2 Laboratoire de Mathématiques

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.


Volume: DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems
Section: Proceedings
Published on: January 1, 2011
Imported on: January 31, 2017
Keywords: 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]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1001.5471
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.tcs.2011.02.024
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1001.5471
  • 10.1016/j.tcs.2011.02.024
  • 10.48550/arxiv.1001.5471
  • 1001.5471
Bulking II: Classifications of cellular automata

Consultation statistics

This page has been seen 182 times.
This article's PDF has been downloaded 189 times.