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.
Type de document :
Communication dans un congrès
STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2015, München, Germany. 32nd International Symposium on Theoretical Aspects of Computer Science, 30, pp.367-378, 2015, 〈http://wwwmayr.in.tum.de/konferenzen/STACS2015/〉. 〈10.4230/LIPIcs.STACS.2015.367〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01476808
Contributeur : Victor Poupet <>
Soumis le : samedi 25 février 2017 - 21:06:28
Dernière modification le : lundi 16 juillet 2018 - 16:24:02
Document(s) archivé(s) le : vendredi 26 mai 2017 - 12:25:32

Fichier

27.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. Comparing 1D and 2D Real Time on Cellular Automata. STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2015, München, Germany. 32nd International Symposium on Theoretical Aspects of Computer Science, 30, pp.367-378, 2015, 〈http://wwwmayr.in.tum.de/konferenzen/STACS2015/〉. 〈10.4230/LIPIcs.STACS.2015.367〉. 〈lirmm-01476808〉

Partager

Métriques

Consultations de la notice

76

Téléchargements de fichiers

223