A synchronization problem in cellular automata has been known as the Firing Squad Synchronization Problem (FSSP), where the FSSP gives a finite-state protocol for synchronizing a large scale of cellular automata. A quest for smaller state FSSP solutions has been an interesting problem for a long time. It has been shown by Balzer [1], Sanders [13], Berthiaume et al. [2], and Ng [12] that there exists no 4-state FSSP solution for arrays and rings. The number four is the state lower bound in the class of FSSP protocols. Umeo et al. [17], by introducing a concept of full versus partial FSSP solutions, provided a list of the smallest 4-state symmetric powers-of-2 FSSP protocols that can synchronize any one-dimensional (1D) ring cellular automata of length \(n=2^{k}\) for any positive integer \(k \ge 1\) . Afterwards, Ng [12] also added a list of asymmetric FSSP partial solutions, thus completing the 4-state powers-of-2 FSSP partial solutions. In this article we present a survey on recent developments in the quest of the smallest 4-state partial solutions for rings.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Class of the Smallest 4-State FSSP Partial Solutions for Rings—A Survey

  • Hiroshi Umeo,
  • Naoki Kamikawa,
  • Gen Fujita

摘要

A synchronization problem in cellular automata has been known as the Firing Squad Synchronization Problem (FSSP), where the FSSP gives a finite-state protocol for synchronizing a large scale of cellular automata. A quest for smaller state FSSP solutions has been an interesting problem for a long time. It has been shown by Balzer [1], Sanders [13], Berthiaume et al. [2], and Ng [12] that there exists no 4-state FSSP solution for arrays and rings. The number four is the state lower bound in the class of FSSP protocols. Umeo et al. [17], by introducing a concept of full versus partial FSSP solutions, provided a list of the smallest 4-state symmetric powers-of-2 FSSP protocols that can synchronize any one-dimensional (1D) ring cellular automata of length \(n=2^{k}\) for any positive integer \(k \ge 1\) . Afterwards, Ng [12] also added a list of asymmetric FSSP partial solutions, thus completing the 4-state powers-of-2 FSSP partial solutions. In this article we present a survey on recent developments in the quest of the smallest 4-state partial solutions for rings.