A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2016

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

Anaël Grandjean
  • Function : Author
  • PersonId : 998304
Victor Poupet

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.
Fichier principal
Vignette du fichier
LIPIcs-ICALP-2016-115.pdf (3.02 Mo) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Licence

Identifiers

Cite

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 View
154 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More