Comparing 1D and 2D Real Time on Cellular Automata

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 : We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the question of determining whether every language that can be recognized in real time on a 2-dimensional CA working on the Moore neighborhood can also be recognized in real time by a 1-dimensional CA working on the standard two-way neighborhood. We show that 2-dimensional CA in real time can perform a linear number of simulations of a 1-dimensional real time CA. If the two classes are equal then the number of simulated instances can be polynomial.
Document type :
Conference papers
Complete list of metadatas

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

File

27.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. Comparing 1D and 2D Real Time on Cellular Automata. STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2015, München, Germany. pp.367-378, ⟨10.4230/LIPIcs.STACS.2015.367⟩. ⟨lirmm-01476808⟩

Share

Metrics

Record views

179

Files downloads

305