Paper Info
Title
Several new generalized linear- and optimum-time synchronization algorithms for two-dimensional rectangular arrays
Abstract
We propose several new generalized synchronization algorithms for 2-D cellular arrays. Firstly, a generalized linear-time synchronization algorithm and its 14-state implementation are given. It is shown that there exists a 14-state 2-D CA that can synchronize any m × n rectangular array in m + n + max(r + s , m + n – r – s + 2) – 4 steps with the general at an arbitrary initial position (r, s),where 1 ≤ r ≤ m, 1 ≤ s ≤ n. The generalized linear-time synchronization algorithm is interesting in that it includes an optimum-step synchronization algorithm as a special case where the general is located at one corner. In addition, we propose a noveloptimum-time generalized synchronization scheme that can synchronize any m × n array in m+n+max (m, n)− min (r, m−r+1)− min (s, n−s+1)−1 optimum steps.
Year
DOI
Venue
2004
10.1007/978-3-540-31834-7_18
MCU
Keywords
Field
DocType
two-dimensional rectangular array,optimum-step synchronization algorithm,generalized linear-time synchronization algorithm,new generalized synchronization algorithm,2-d cellular array,14-state implementation,14-state 2-d ca,arbitrary initial position,n rectangular array,n array,noveloptimum-time generalized synchronization scheme,optimum-time synchronization algorithm,linear time
Discrete mathematics,Synchronization,Combinatorics,Time synchronization,Firing squad synchronization problem,Algorithm,Time complexity,Synchronization algorithm,Rectangular array,Mathematics
Conference
Volume
ISSN
ISBN
3354
0302-9743
3-540-25261-4
Citations 
PageRank 
References 
16
0.80
14
Authors
4
Name
Order
Citations
PageRank
Hiroshi Umeo136153.61
Masaya Hisaoka2724.26
Masato Teraoka3331.59
Masashi Maeda4604.28