Leader election on two-dimensional periodic cellular automata

详细信息    查看全文

• 作者：Nicolas Bacquey ^{nicolas.bacquey@unicaen.fr}
• 关键词：Cellular automata ; Leader election ; Bi-periodical configuration ; Equivalence classes ; Uniform computation
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：659
• 期：Complete
• 页码：36-52
• 全文大小：678 K
• 卷排序：659

文摘

This article explores the computational power of bi-dimensional cellular automata acting on periodical configurations. It extends in some sense the results of a similar paper dedicated to the one-dimensional case. More precisely, we present an algorithm that computes a “minimal pattern network”, i.e. a minimal pattern and the two translation vectors it can use to tile the entire configuration. This problem is equivalent to the computation of a leader, which is one equivalence class of the cells of the periodical configuration.