Comparing 1D and 2D Real Time on Cellular Automata - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

Comparing 1D and 2D Real Time on Cellular Automata

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

Résumé

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

Dates et versions

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

Licence

Paternité

Identifiants

Citer

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⟩
245 Consultations
199 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More