The structure of communication problems in cellular automata

Abstract : 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.
Type de document :
Communication dans un congrès
Fatès, Nazim and Goles, Eric and Maass, Alejandro and Rapaport, Iván. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.59-76, 2011, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01196144
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 9 septembre 2015 - 11:15:04
Dernière modification le : jeudi 11 janvier 2018 - 06:20:36
Document(s) archivé(s) le : lundi 28 décembre 2015 - 23:02:12

Fichier

dmAP0105.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196144, version 1

Collections

Citation

Raimundo Briceño, Pierre-Etienne Meunier. The structure of communication problems in cellular automata. Fatès, Nazim and Goles, Eric and Maass, Alejandro and Rapaport, Iván. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.59-76, 2011, DMTCS Proceedings. 〈hal-01196144〉

Partager

Métriques

Consultations de la notice

246

Téléchargements de fichiers

96