Résumé: The capability of one-way (space-bounded) cellular automata (OCA) to time-compute functions is investigated. That means given a constant input of length n a distinguished cell has to enter a distinguished state exactly after f(n) time steps. The family of such functions (C(OCA)) is characterized in terms of formal language recognition. Several functions are proved to be time-computable and properties of C(OCA) are given. The time-computation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time.

Langue: Anglais