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
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