广西师范大学学报（自然科学版） ›› 2013, Vol. 31 ›› Issue (1): 37-43.

• • 上一篇    下一篇

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

翟莹1, 易忠1, 谢正卫2, 邓培民1, 李王月3   

  1. 1.广西师范大学数学科学学院,广西桂林541004;
    2.江苏技术师范学院数理学院,江苏常州213001;
    3.广西计算中心,广西南宁530022
  • 收稿日期:2012-09-30 出版日期:2013-03-20 发布日期:2018-11-26
  • 通讯作者: 翟莹(1980—),女,广西桂林人,广西师范大学讲师。E-mail:zhaizhai1029@tom.com
  • 基金资助:
    国家自然科学基金资助项目(11161005);广西自然科学基金资助项目(0832103,2010GXNSFA013118);广西教育厅科研项目资助项目(201106LX074)

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

ZHAI Ying1, YI Zhong1, XIE Zheng-wei2, DENG Pei-min1, LI Yue3   

  1. 1.College of Mathematical Science,Guangxi Normal University,Guilin Guangxi 541004,China;
    2.School of Mathematics and Physics,Jiangsu Teachers University of Technology,Changzhou Jiangsu 213001,China;
    3.Guangxi Computing Center,Nanning Guangxi,530022,China
  • Received:2012-09-30 Online:2013-03-20 Published:2018-11-26

摘要： 无前像位形(GOE)是元胞自动机的一个重要特征,它的存在关系到元胞自动机的可逆性。本文主要利用矩阵代数的原理,针对一类二元域上的特殊混合规则的线性二维元胞自动机进行讨论,给出了在不同的情况下,一个位形是GOE的充分必要条件,以及计算元胞自动机中GOE的个数的算法。

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

Abstract: 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) (theGalois field with two elements) by using matrix algebra.Several necessary and sufficient conditions are provided,which guarantee a given configuration of beinga 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.

Key words: cellular automata, Garden of Eden, hybrid cellular automata, matrix algebra

中图分类号: 

  • TP301.1
[1] JADUR C,YAZLLE J.On the dynamics of cellular automata inducedfrom a prefix code[J].Advances in Applied Mathematics,2007,38(1):27-53.
[2] 平萍,周曜,张宏,等.可逆元胞自动机加密技术研究[J].通信学报,2008,29(5):26-33.
[3] 白克钊,罗旭东,孔令江,等.开放边界条件下一种数据传输元胞自动机模型[J].广西师范大学学报:自然科学版,2010,28(3):1-4.
[4] 张旭,任卫,唐冬妮,等.基于改进元胞自动机的数字保密通信方案[J].物理学报,2010,59(8):5281-5287.
[5] 潘江洪,白克钊,邝华,等.一种考虑能见度影响的元胞自动机交通流模型[J].广西师范大学学报:自然科学版,2011,29(3):1-4.
[6] 覃松,邓敏艺,孔令江.融资融券影响的元胞自动机股票市场模拟研究[J].广西师范大学学报:自然科学版,2011,29(4):12-15.
[7] AKIN H,SIAP I.On cellular automata over Galois rings[J].Information Processing Letters,2007,103(1):24-27.
[8] 邓婷,易忠,邓培民.状态机的稳定状态与稳定子集[J].广西师范大学学报:自然科学版,2005,23(3):29-32.
[9] INOKUCHI S.On behaviors of cellular automata with rule 156[J].Bulletin of Informatics and Cybernetics,1998,30(1):121-131.
[10] 朱留华,吕集尔,郑容森,等.一维五邻居元胞自动机的演化行为[J].系统工程,2008,26(10):119-122.
[11] 秦大康,江志松.7号初等元胞自动机生成的时间序列的复杂性分析[J].华东师范大学学报:自然科学版,2008(3):75-82,102.
[12] 戴燕红,孙克文,王益.126号初等元胞自动机的演化语言复杂性[J].苏州大学学报:自然科学版,2010,26(3):29-34.
[13] KHAN A R,CHOUDHURY P P,DIHIDAR K,et al.VLSI architecture of a cellular automata[J].Computers and Mathematics with Applications,1997,33(5):79-94.
[14] KHAN A R,CHOUDHURY P P,DIHIDAR K,et al.Text compression using two dimensional cellular automata[J].Computers and Mathematics with Applications,1999,37(6):115-127.
[15] DIHIDAR K,CHOUDHURY P P.Matrix algebraic formulae concerning some exceptional rules of two-dimensional cellular automata[J].Information Science,2004,165(1/2):91-101.
[16] CHATTOPADHYAY P,CHOUDHURY P P,DIHIDAR K.Characterisation of aparticular hybrid transformation of two-dimensional cellular automata[J].Computers and Mathematics with Applications,1999,38(5/6):207-216.
[17] ZHAI Ying,YI Zhong,DENG Pei-min.On behavior of two-dimensionalcellular automata with an exceptional rule[J].Information Science,2009,179(5):613-622.
[18] ZHAI Ying,YI Zhong,DENG Pei-min.On behavior of two-dimensionalcellular automata with an exceptional rule under periodic boundary condition[J].The Journal ofChina Universities of Posts and Telecommunications,2010,17(1):67-72.
[19] SIAP I,AKIN H,SAH F.Characterization of two dimensional cellular automata over ternary fields[J].Journal of the Franklin Institute,2011,348(7):1258-1275.
[20] SIAP I,AKIN H,SAH F.Garden of eden configurations for 2-D cellular automata with rule 2460N[J].Information Science,2010,180(18):3562-3571.
[21] AMOROSO S,COOPER G,PATT Y.Some clarifications of the conceptof a Garden-of-Eden configuration[J].Journal of Computer and System Sciences,1975,10(1):77-82.
[1] 邝先验, 陈自如. 考虑礼让行人的交叉口机非混合交通流模型[J]. 广西师范大学学报（自然科学版）, 2019, 37(4): 1-15.
[2] 张学良,谭惠丽,白克钊,唐国宁,邓敏艺. 一种体现心肌细胞传导记忆的元胞自动机模型[J]. 广西师范大学学报（自然科学版）, 2017, 35(4): 1-9.
[3] 黄雯, 谭惠丽. 心脏记忆对螺旋波动力学的影响[J]. 广西师范大学学报（自然科学版）, 2017, 35(2): 1-8.
[4] 戴静娱, 张学良, 邓敏艺, 谭惠丽. 位置扰动对激发介质中螺旋波动力学行为的影响[J]. 广西师范大学学报（自然科学版）, 2016, 34(2): 8-14.
[5] 蔡美静, 邝华, 白克钊, 陈若航. 电影厅内部布局及出口位置对疏散效率的影响[J]. 广西师范大学学报（自然科学版）, 2015, 33(3): 1-6.
[6] 邝先验, 吴赟, 曹韦华, 吴银凤. 城市混合非机动车流的元胞自动机仿真模型[J]. 广西师范大学学报（自然科学版）, 2015, 33(1): 7-14.
[7] 师伟展, 邝华, 白克钊, 孔令江. 固执者对舆论传播动力学的影响研究[J]. 广西师范大学学报（自然科学版）, 2014, 32(3): 22-26.
[8] 许钢, 刘海燕, 张超英, 梁振燕. 基于元胞自动机的建构主义理论应用模拟[J]. 广西师范大学学报（自然科学版）, 2013, 31(4): 7-12.
[9] 邓敏艺, 谭惠丽. 一个双变量元胞自动机模型的定性研究[J]. 广西师范大学学报（自然科学版）, 2013, 31(2): 1-6.
[10] 余艳, 白克钊, 孔令江. 行人与机动车相互干扰的元胞自动机模拟研究[J]. 广西师范大学学报（自然科学版）, 2013, 31(1): 6-10.
[11] 覃松, 邓敏艺, 孔令江. 融资融券影响的元胞自动机股票市场模拟研究[J]. 广西师范大学学报（自然科学版）, 2011, 29(4): 12-15.
[12] 潘江洪, 白克钊, 邝华, 孔令江. 一种考虑能见度影响的元胞自动机交通流模型[J]. 广西师范大学学报（自然科学版）, 2011, 29(3): 1-4.
[13] 陈永淇, 白克钊, 邝华, 孔令江, 刘慕仁. 教室内布局对人员疏散影响的研究[J]. 广西师范大学学报（自然科学版）, 2011, 29(1): 1-4.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发