Differences Between 2D Neighborhoods According to Real Time Computation - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2017

Differences Between 2D Neighborhoods According to Real Time Computation

Anaël Grandjean
  • Function : Author
  • PersonId : 998304

Abstract

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).
No file

Dates and versions

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

Identifiers

Cite

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 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More