A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods

Anaël Grandjean 1 Victor Poupet 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods, no general construction was known. We present here a technique of linear acceleration for all two-dimensional languages recognized by cellular automata working on complete neighborhoods.
Type de document :
Communication dans un congrès
ICALP: International Colloquium on Automata, Languages and Programming, Jul 2016, Roma, Italy. 43rd International Colloquium on Automata, Languages, and Programming, 55, pp.115:1--115:12, 2016, Leibniz International Proceedings in Informatics (LIPIcs). 〈http://www.easyconferences.eu/icalp2016/〉. 〈10.4230/LIPIcs.ICALP.2016.115〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01476809
Contributeur : Victor Poupet <>
Soumis le : samedi 25 février 2017 - 21:10:56
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : vendredi 26 mai 2017 - 12:18:11

Fichier

LIPIcs-ICALP-2016-115.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Anaël Grandjean, Victor Poupet. A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods. ICALP: International Colloquium on Automata, Languages and Programming, Jul 2016, Roma, Italy. 43rd International Colloquium on Automata, Languages, and Programming, 55, pp.115:1--115:12, 2016, Leibniz International Proceedings in Informatics (LIPIcs). 〈http://www.easyconferences.eu/icalp2016/〉. 〈10.4230/LIPIcs.ICALP.2016.115〉. 〈lirmm-01476809〉

Partager

Métriques

Consultations de la notice

103

Téléchargements de fichiers

111