Paper Info
Title
Some New Generalized Synchronization Algorithms and Their Implementations for Large Scale Cellular Automata
Abstract
In this paper, we study a generalized synchronization problem for large scale cellular automata (CA) on one- and two- dimensional arrays. Some new generalized synchronization algorithms will be designed both on O(1)-bit and 1-bit inter-cell communication models of cellular automata. We give a 9-state and 13-state CA that can solve the generalized synchronization problem in optimum- and linear-time on O(1)-bit 1-D and 2-D CA, respectively. The number of internal states of the CA implemented is the smallest one known at present. In addition, it is shown that there exists a 1-bit inter-cell communication CA that can synchronize 1-D n cells with the general on the kth cell in n+max(k, n - k + 1) steps, which is two steps larger than the optimum time. We show that there still exist several new generalized synchronization algorithms, although more than 40 years have passed since the development of the problem.
Year
DOI
Venue
2002
10.1007/3-540-45833-6_23
UMC
Keywords
Field
DocType
new generalized synchronization algorithms,large scale cellular automata,new generalized synchronization algorithm,cellular automaton,1-bit inter-cell communication ca,optimum time,1-d n cell,generalized synchronization problem,1-bit inter-cell communication model,13-state ca,dimensional array,2-d ca,cell communication,linear time,cellular automata
Cellular automaton,Discrete mathematics,Synchronization,Existential quantification,Mobile automaton,Computer science,Models of communication,Synchronization algorithm
Conference
Volume
ISSN
ISBN
2509
0302-9743
3-540-44311-8
Citations 
PageRank 
References 
6
0.52
12
Authors
5
Name
Order
Citations
PageRank
Hiroshi Umeo136153.61
Masaya Hisaoka2724.26
Koshi Michisaka3121.48
Koji Nishioka460.52
Masashi Maeda5604.28