Title :
A state-change complexity in synchronization algorithms for cellular automata
Author :
Matsumoto, Kouhei ; Umeo, Hiroshi
Author_Institution :
Osaka Electro-Commun. Univ., Japan
Abstract :
This paper presents a comparative study of state-change complexity in optimum- and linear-time synchronization algorithms for a large-scale of cellular automata. We implement most of the synchronization algorithms developed so far and investigate their state-change complexities on a computer. The state-change complexity in several synchronization algorithms on two-dimensional arrays is also studied.
Keywords :
cellular automata; computational complexity; synchronisation; autonomous decentralized systems; cellular automata; firing squad synchronization algorithm; state-change complexity; synchronization algorithm; two-dimensional array;
Conference_Titel :
SICE 2004 Annual Conference
Conference_Location :
Sapporo
Print_ISBN :
4-907764-22-7
