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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01476809
Contributor : Victor Poupet <>
Submitted on : Saturday, February 25, 2017 - 9:10:56 PM
Last modification on : Monday, July 16, 2018 - 4:24:02 PM
Long-term archiving on : Friday, May 26, 2017 - 12:18:11 PM

File

LIPIcs-ICALP-2016-115.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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. pp.115:1--115:12, ⟨10.4230/LIPIcs.ICALP.2016.115⟩. ⟨lirmm-01476809⟩

Share

Metrics

Record views

242

Files downloads

246