A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

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

Anaël Grandjean
  • Fonction : Auteur
  • PersonId : 998304
Victor Poupet

Résumé

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.
Fichier principal
Vignette du fichier
LIPIcs-ICALP-2016-115.pdf (3.02 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01476809 , version 1 (25-02-2017)

Licence

Paternité

Identifiants

Citer

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. pp.115:1--115:12, ⟨10.4230/LIPIcs.ICALP.2016.115⟩. ⟨lirmm-01476809⟩
238 Consultations
152 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More