Complex Systems

Language Recognizable in Real Time by Cellular Automata Download PDF

Véronique Terrier
LAIAC, Université de Caen,
Esplanade de la Paix, 14032 Caen, France

Abstract

We consider the language of the strings over the alphabet of shape where is the length of the string . We show that is recognized in real time by an iterative array but not by a one-way cellular automaton, while the language is recognized in real time by a cellular automaton but not by an iterative array.