A New Time-Optimum Synchronization Algorithm for Two-Dimensional Cellular Arrays

Authors :: Hiroshi Umeo
Hiroki Uchino
Source :: Computer Aided Systems Theory – EUROCAST 2007 ISBN: 9783540758662, EUROCAST
Publication Year :: 2007
Publisher :: Springer Berlin Heidelberg, 2007.
Abstract: The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed so far. In the present paper, we propose a new optimum-time algorithm for synchronizing two-dimensional cellular automata. The algorithm can synchronize any rectangular array of size m × n in optimum m + n + max(m, n) - 3 steps.

Subjects :: Cellular array
Firing squad synchronization problem
Computer science
Rectangular array
Synchronizing
Synchronization algorithm
Nonlinear Sciences::Cellular Automata and Lattice Gases
Algorithm
Computer Science::Formal Languages and Automata Theory
Cellular automaton

ISBN :: 978-3-540-75866-2
ISBNs :: 9783540758662
Database :: OpenAIRE
Journal :: Computer Aided Systems Theory – EUROCAST 2007 ISBN: 9783540758662, EUROCAST
Accession number :: edsair.doi...........64c6a85c7e76d3e7dd153a32e5e98965
Full Text :: https://doi.org/10.1007/978-3-540-75867-9_76

Full Text Access

Tools