Developments of Smallest Synchronization Protocols and Its Application to Multi-Dimensional Cellular Arrays

最小同步协议的发展及其在多维蜂窝阵列中的应用

• 批准号: 21500023
• 负责人: UMEO Hiroshi
• 金额: $ 2.5万
• 依托单位: Osaka Electro-Communication University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500023/
• 关键词: オートマトン理論・形式言語理論; アルゴリズム理論; セルオートマトン; 一斉射撃問題; 複雑系; Dynamical System; FSSP; アルゴリズム; セルラーオートマトン

We study a firing squad synchronization problem(FSSP) that gives a finite-state protocol for synchronizing cellular automata(CA). In this research project, we made an investigation into smaller FSSP solutions not only for one-dimensional(1D) but multi-dimensional CAs. We present a class of smallest 4-state partial solutions for 1D the CAs. It is shown that there exists a 7-state square synchronizer for 2D square arrays, which is a smallest solution for square arrays, known at present. We also show that there exists a nine-state FSSP solution for 2D rectangular arrays. In the last, we have proposed a new class of optimum-time multi-dimensional FSSP algorithms based on recursive-halving marking.

我们研究了一个行刑队同步问题（FSSP），给出了一个有限状态协议同步元胞自动机（CA）。在这个研究项目中，我们调查了更小的FSSP解决方案，不仅一维（1D），但多维CA。本文给出了一维CA的一类最小四态部分解。本文证明了二维方阵存在一个七态的方阵同步器，这是目前已知的方阵的最小解。我们还表明，存在一个九状态FSSP解决方案的二维矩形阵列。最后，我们提出了一类新的基于递归减半标记的最优时间多维FSSP算法。

项目成果

Proceedings for 9th International Conference on Cellular Automata for Research and Industry ACRI 2010

第九届国际元胞自动机研究与工业会议 ACRI 2010 论文集

• 发表时间: 2010
• 作者: S. Bandini;S. Manzoni;H. Umeo;and G. Vizzari
• 通讯作者: and G. Vizzari

Two-dimensional cellular automata synchronizers

二维元胞自动机同步器

• 发表时间: 2010
• 期刊: Proc. of the 4th WSEAS International Conference on Computational Intelligence
• 作者: 金石煥;高橋伸;田中二郎;H. Umeo
• 通讯作者: H. Umeo

Cellular Automata. Encyclopedia of Designs in Forms and Functions

元胞自动机。

• 发表时间: 2011
• 作者: 藤原拓也;南出靖彦;H. Umeo
• 通讯作者: H. Umeo

セルオートマトン

元胞自动机

• 发表时间: 2011
• 作者: 梅尾;F. Peper;足立;磯川;今井;小松崎;J. Lee
• 通讯作者: J. Lee

A New Optimum-time Firing Squad Synchronization Algorithms for Two-Dimensional Rectangle Arrays-Freezing-Thawing Technique Based-

一种基于冻融技术的二维矩形阵列最佳时间射击班同步算法

• 发表时间: 2010
• 期刊: Proceedings of the 2010 International Conference on High Performance Computing and Simulation HPCS 2010
• 作者: H.Umeo;T.Yamawaki;K.Nishide
• 通讯作者: K.Nishide