Differences Between 2D Neighborhoods According to Real Time Computation - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Differences Between 2D Neighborhoods According to Real Time Computation

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

Résumé

Cellular automata are a parallel model of computation. This paper presents studies about the impact of the choice of the neighborhood on small complexity classes, mainly the real time class. The main result states that given two neighborhoods $N$ and $N’$, if $N$ has a limiting vertex in some direction and $N’$ have no vertex in that direction then there is a language recognizable in real time with $N’$ and not with $N$. One easy corollary is that real time classes for two neighborhoods may be incomparable (and such neighborhoods are easy to construct).
Fichier non déposé

Dates et versions

lirmm-01693188 , version 1 (25-01-2018)

Identifiants

Citer

Anaël Grandjean. Differences Between 2D Neighborhoods According to Real Time Computation. DLT 2017 - International Conference on Developments in Language Theory, Aug 2017, Liège, Belgium. pp.198-209, ⟨10.1007/978-3-319-62809-7_14⟩. ⟨lirmm-01693188⟩
82 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More