On the complexity of two-dimensional signed majority cellular automata
作者：
Highlights：
• The introduction of the family of signed majority cellular automata (SMCA).
• Dynamics of the family of SMCA and their computational complexity.
• A general framework that relates circuit simulation with CA complexity.
• Examples of SMCA that are Turing-Universal and Intrinsic-Universal.
• Three equivalence classes of uniform SMCA: symmetric, antisymmetric and asymmetric.
摘要
•The introduction of the family of signed majority cellular automata (SMCA).•Dynamics of the family of SMCA and their computational complexity.•A general framework that relates circuit simulation with CA complexity.•Examples of SMCA that are Turing-Universal and Intrinsic-Universal.•Three equivalence classes of uniform SMCA: symmetric, antisymmetric and asymmetric.
论文关键词：Cellular automata dynamics,Majority cellular automata,Signed two-dimensional lattice,Turing universal,Intrinsic universal,Computational complexity
论文评审过程：Received 16 May 2016, Revised 3 July 2017, Accepted 10 July 2017, Available online 6 September 2017, Version of Record 5 October 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.07.010
