Linear speed-up without synchronization on one dimensional cellular automata

O. HEEN

IBP-Litp 1995/57: Rapport de Recherche Litp / Litp research reports
9 pages - Novembre/November 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Linear speed-up without synchronization on one dimensional cellular automata

Résumé : Nous présentons une nouvelle preuve du théorème d'accélération linéaire pour les automates cellulaires, qui n'utilise ni synchronisation (comme dans Ibarra et al.) ni machine séquentielle (comme dans Mazoyer et Reimen). La méthode employée consiste à plonger tout diagramme espace-temps dans un émulateur en gérant les déplacements d'information. Comme Ð effet de bord ð , le nombre d'états nécessaires pour accélérer tombe à s + 2.s2.

Abstract : We give a new proof to the well known linear speed-up theorem for cellular automata, which does not require any synchronization (as in Ibarra and al.) nor the use of a sequential device . The simulation method consists in embeding any space-time diagram in an emulating one with appropriate moves of information. As a side effect, the number of states needed to perform the speed-up is lowered to s + 2.s2

Publications internes Litp 1995 / Litp research reports 1995