Content
Title
Cellular Automata: Real Time and Neighborhoods
Keywords
Cellular automata, neighborhoods, language recognition, any dimension, real time, convex hull, linear speed-up, constant speed-up.
Abstract
In this thesis we have worked on the impact of the choice of a neeighborhood on the algorithmic abilities of cellular automata. We have specifically studied the lower complexity classes such as the real time (that corresponds to the shortest time necessary for a cellular automaton to read all the letters of the input word) and the real time plus a constant. It is indeed known that neighborhoods are equivalent in linear time and it is therefore necessary to consider shorter times.
We have obtained neighborhood equivalence results with respect to the real time (neighborhood classes such that cellular automata working on any of those neighborhoods can recognize the same languages in real time) and linear or constant speed-up theorems for many classes of neighborhoods.
A more detailed abstract is available (in French).
Report
Most Recent Version (in French) [PDF]
Updated version with hyperlinks.
General information
Laboratory
Laboratoire de l'Informatique du Parallélisme (LIP) at the Ecole normale supérieure de Lyon (ENS Lyon)
Advisors
Jacques Mazoyer and Marianne Delorme
Jury
- Bruno Durand
- Etienne Grandjean (reviewer)
- Martin Kutrib
- Kenichi Morita (reviewer)
- Véronique Terrier (invited member)
Date and Location of Defence
December 8th 2006, ENS Lyon (France)