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

Synthesis of the Homogeneous Cellular Automata with Two Predecessors of Reachable State

作　　者：张传武[1] 

机构地区：[1]西南民族大学电气信息工程学院,成都610041

出　　处：《计算机科学》2008年第4期184-185,189,共3页Computer Science

基　　金：国家自然科学基金项目(资助号60603009)

摘　　要：用状态转移矩阵方程表示加性细胞自动机的状态转移,通过状态转移矩阵及其特征多项式来分析加性细胞自动机的状态转移特性,从而求出其状态转移图。2k-1单元的零边界90线性细胞自动机的状态转移矩阵的秩为2k-2,从而可以确定其状态转移图具有二叉树型结构。同时,根据其状态转移矩阵方程可以求出2k-1单元的零边界90线性细胞自动机对应的22k-1个2k-1单元的零边界90加性细胞自动机具有相同的状态转移结构,即这22k-1个90加性细胞自动机同构。这样可系统构造一簇具有相同二叉树型状态转移结构的细胞自动机。The state transition diagram of additive cellular automata can be expressed by the matrix equation. The state transition diagram can be presented by the analysis of state transition matrix and its characteristic polynomial. The rank of 2^k -1 cells null boundary 90 linear cellular automata is equal to 2^k -2, so every reachable state has two predecessors, thus the transition diagram is binary tree type. And according to the transition matrix equation, we can determine that the 2^2k-1 null boundary 90 additive cellular automata with 2^k -1 cells corresponding to the 2^k -1 cells null boundary 90 linear cellular automata have the same structure of state transition, which means they have homogeneous characteristic. Thus we can synthesize a family of cellular automata whose state transition diagram is identical and has the form of binary tree type.

关 键 词：细胞自动机 状态转移图 二叉树 同构 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构] TP311.13[自动化与计算机技术—计算机科学与技术]