A State-Efficient Zebra-Like Implementation of Synchronization Algorithms for 2D Rectangular Cellular Arrays
2012
Hiroshi Umeo | A. Nomura
The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms has been proposed for not only one-dimensional (1D) but two-dimensional (2D) arrays. In the present paper, we propose a simple and state-efficient mapping scheme: zebra-like mapping for implementing 2D synchronization algorithms for rectangular arrays. The zebra-like mapping we propose embeds two types of configurations alternately onto a 2D array like a zebra pattern, one configuration is a synchronization configuration of 1D arrays and the other is a stationary configuration which keeps its state unchanged until the final synchronization. It is shown that the mapping gives us a smallest, known at present, implementation of 2D FSSP algorithms for rectangular arrays. The implementation itself has a nice property that the correctness of the constructed transition rule set is clear and transparent. It is shown that there exists a nine-state 2D cellular automaton that can synchronize any (m x n) rectangle in (m+n+max(m,n)-3) steps.
Show more [+] Less [-]AGROVOC Keywords
Bibliographic information
This bibliographic record has been provided by Directory of Open Access Journals
