二叉树型结构的细胞自动机同构性构造

摘要

用状态转移矩阵方程表示加性细胞自动机的状态转移,通过状态转移矩阵及其特征多项式来分析加性细胞自动机的状态转移特性,从而求出其状态转移图.2k-1单元的零边界90线性细胞自动机的状态转移矩阵的秩为2k-2,从而可以确定其状态转移图具有二叉树型结构.同时,根据其状态转移矩阵方程可以求出2k-1单元的零边界90线性细胞自动机对应的22k-1个2k-1单元的零边界90加性细胞自动机具有相同的状态转移结构,即这22k-1个90加性细胞自动机同构.这样可系统构造一簇具有相同二叉树型状态转移结构的细胞自动机.