Summary
International Symposium on Nonlinear Theory and its Applications
2009
Session Number:B4L-A
Session:
Number:B4L-A2
Small Non-Optimum-Time Firing Squad Synchronization Protocols for One-Dimensional Rings
Hiroshi UMEO, Jean-Baptiste YUNES, Naoki KAMIKAWA, Juntarou KURASHIKI,
pp.-
Publication Date:2009/10/18
Online ISSN:2188-5079
Summary:
The synchronization in cellular automata has been known as a firing squad synchronization problem since its development, in which it was originally proposed by J. Myhill in Moore [1964] to synchronize all or some parts of self-reproducing cellular automata. The firing squad synchronization problem has been studied extensively for more than 40 years [1-22]. In the present article, we propose two six-state firing squad synchronization full protocols for rings, which are the smallest ones known at present for rings. In addition, we present a family of 4-state partial protocols that can synchronize any one-dimensional rings of length n = 2k for any positive integer k. The number four is the smallest one in the class of synchronization protocols proposed so far. We also study state change complexities for those protocols.