A Simple Optimum-Time FSSP Algorithm for Multi-Dimensional Cellular Automata

Autor:	Umeo, Hiroshi, Nishide, Kinuo, Kubo, Keisuke
Rok vydání:	2012
Předmět:	Computer Science - Formal Languages and Automata Theory Computer Science - Discrete Mathematics Computer Science - Data Structures and Algorithms Nonlinear Sciences - Cellular Automata and Lattice Gases F.1.1 F.1.2 F.1.3
Zdroj:	EPTCS 90, 2012, pp. 151-165
Druh dokumentu:	Working Paper
DOI:	10.4204/EPTCS.90.13
Popis:	The firing squad synchronization problem (FSSP) on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed for not only one-dimensional arrays but two-dimensional arrays. In the present paper, we propose a simple recursive-halving based optimum-time synchronization algorithm that can synchronize any rectangle arrays of size m*n with a general at one corner in m+n+max(m, n)-3 steps. The algorithm is a natural expansion of the well-known FSSP algorithm proposed by Balzer [1967], Gerken [1987], and Waksman [1966] and it can be easily expanded to three-dimensional arrays, even to multi-dimensional arrays with a general at any position of the array. Comment: In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1208.2761 Zobrazit plný text záznamu View this record from Arxiv