Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438128 | Theoretical Computer Science | 2014 | 10 Pages |
Abstract
Classical cellular automata have a single, global clock that allows all the cells to update their states simultaneously at every clock cycle. Here, we overturn this assumption and we study cellular automata where different cells can use different clocks cycles and, as a consequence, they update at different times. We show how it is possible to solve the firing squad synchronization problem in this new setting and propose a synchronization algorithm operating in time linear with respect to the automata size.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Luca Manzoni, Hiroshi Umeo,