一类特殊规则的二维混合元胞自动机的GOE问题  

Garden of Eden Configurations of a Particular Hybrid Transformation of Two-dimensional Cellular Automata

作　　者：翟莹[1] 易忠[1] 谢正卫[2] 邓培民[1] 李玥[3] 

机构地区：[1]广西师范大学数学科学学院,广西桂林541004 [2]江苏技术师范学院数理学院,江苏常州213001 [3]广西计算中心,广西南宁530022

出　　处：《广西师范大学学报（自然科学版）》2013年第1期37-43,共7页Journal of Guangxi Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(11161005);广西自然科学基金资助项目(0832103;2010GXNSFA013118);广西教育厅科研项目资助项目(201106LX074)

摘　　要：无前像位形(GOE)是元胞自动机的一个重要特征,它的存在关系到元胞自动机的可逆性。本文主要利用矩阵代数的原理,针对一类二元域上的特殊混合规则的线性二维元胞自动机进行讨论,给出了在不同的情况下,一个位形是GOE的充分必要条件,以及计算元胞自动机中GOE的个数的算法。Garden of Eden （GOE） configuration is an important characteristic in cellular automata （CA） theory. Its existence relates to the reversibility of a CA. This article deals with a particular hybrid linear two-dimensional （2-D） CA in GF（2） （the Galois field with two elements） by using matrix algebra. Several necessary and sufficient conditions are provided,which guarantee a given configuration of being a GOE in different cases. Besides,the algorithm is proposed to obtain the number of GOEs in such a CA with the particular hybrid rule mentioned above.

关 键 词：元胞自动机 GOE 混合元胞自动机 矩阵代数 

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