Synchronization of a bounded degree graph of cellular automata with nonuniform delays in time

详细信息	查看全文 | 推荐本文 |

• 作者：Serge Grigorieff
• 关键词：Cellular automata ; Synchronization
• 刊名：Theoretical Computer Science
• 出版年：2006
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：5 May 2006
• 卷：356
• 期：1-2
• 页码：170-185
• 文件大小：264 K

摘要

Jiang [The synchronization of non uniform networks of finite automata, in: FOCS, Vol. 89, 1989, pp. 376–381, The synchronization of non uniform networks of finite automata, Inform. and Comput. 97(2) (1992) 234–261] proved a remarkable result: for every k, there exists a cellular automaton synchronizing every degree k connected graph with arbitrary symmetric communication delays. The synchronization time obtained by Jiang is O(Δ³) where Δ is the maximum communication delay between two cells. Mazoyer [Synchronization of a line of finite automata with non uniform delays, 1990, unpublished] proved an O(D²) synchronization time where D is the sum of the communication delays of the degree k connected graph (together with an O(DlogD) synchronization time in case the graph has only two cells).

In this paper, we prove (cf. Theorem 23) that for any m2 one can synchronize in time Dlog_m(D) all lines of total communication delay >m⁹ (shorter lines being synchronized in time 4D). A result which extends to bounded degree connected graphs using Rosensthiel's technique [P. Rosenstiehl, Existence d’automates capables de s’accorder bien qu’arbitrairement connectés et nombreux, Internat. Comput. Center Bull. 5 (1966) 245–261, P. Rosenstiehl, J.R. Fiksel, A. Holliger, Intelligent graphs: networks of finite automata capable of solving graph problems, in: R.C. Read (Ed.), Graph Theory and Computing, Academic Press, New York, 1972, pp. 219–265]. As shown by Vivien [Cellular Automata: A Geometrical Approach, to appear], this result is already optimal for lines of two cells with arbitrary communication delay.

The method relies heavily on Jiang technique of circuit with revolving information.