2020/03/30 by Thomas Worsch, Worsch, Thomas
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Computational Complexity (cs.CC) #DNA and Biological Computing #F.1.1 #F.1.2 #F.1.3 #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2003.13558
openalex publication_date 2020/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In cellular automata with multiple speeds for each cell i there is a\npositive integer pi such that this cell updates its state still periodically\nbut only at times which are a multiple of pi. Additionally there is a finite\nupper bound on all pi. Manzoni and Umeo have described an algorithm for\nthese (one-dimensional) cellular automata which solves the Firing Squad\nSynchronization Problem. This algorithm needs linear time (in the number of\ncells to be synchronized) but for many problem instances it is slower than the\noptimum time by some positive constant factor. In the present paper we derive\nlower bounds on possible synchronization times and describe an algorithm which\nis never slower and in some cases faster than the one by Manzoni and Umeo and\nwhich is close to a lower bound (up to a constant summand) in more cases.\n