Linear Speed-Up for Cellular Automata Synchronizers and Applications

O. Heen

IBP-Litp 1996/14: Rapport de Recherche Litp / Litp research reports
13 pages - Mars/March 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Linear Speed-Up for Cellular Automata Synchronizers and Applications

Résumé : Les automates cellulaires élémentaires peuvent être utilisés comme reconnaisseurs de langages ou comme calculateurs. Il existe plusieurs preuves du théorème d'accélération linéaire pour les reconnaisseurs (cf [6,7,11]).Nous donnons une méthode d'accélération linéaire pour une classe particulière de calculateurs : les synchroniseurs (qui ne sont pas des reconnaisseurs). Une conséquence est l'extension d'un résultat de J. Mazoyer concernant les temps de synchronisation : nous montrons que tout polynôme à coefficients rationnels d'un temps de synchronisation est encore un temps de synchronisation (pour peu qu'il excède un certain minimum).

Abstract : Simple cellular automata can be used as langage recognizers or function calculators. There are several proofs of the linear speed-up theorem for recognizers [6,7,11]. In this paper we design a linear speed-up method for a special kind of calculators, namely the synchronizers, which are dif- ferent from recognizers. As a consequence, we extend a result form J. Mazoyer by proving that any polynomial with rational coefficients of a synchronization time is also a synchronization time (provided that it be greater than a certain minimal time).

Publications internes Litp 1996 / Litp research reports 1996