Journal of Guangxi Normal University(Natural Science Edition) ›› 2013, Vol. 31 ›› Issue (1): 37-43.

Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] KUANG Xianyan, CHEN Ziru. Mixed Traffic Flow Model of Signalized Intersections Involving Pedestrian Comity [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(4): 1-15.
[2] HUANG Wen,TAN Huili. Effect of Cardiac Memory on Spiral Wave [J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(2): 1-8.
[3] DAI Jingyu, ZHANG Xueliang, DENG Minyi, TAN Huili. Effect of Position Perturbation for Spiral Waves in Excitable Media [J]. Journal of Guangxi Normal University(Natural Science Edition), 2016, 34(2): 8-14.
[4] KUANG Xian-yan, WU Yun, CAO Wei-hua, WU Yin-feng. Cellular Automata Simulation Model for Urban MixedNon-motor Vehicle Flow [J]. Journal of Guangxi Normal University(Natural Science Edition), 2015, 33(1): 7-14.
[5] SHI Wei-zhan, KUANG Hua, BAI Ke-zhao, KONG Ling-jiang. Effect of Ramstam People on Opinion Dynamics [J]. Journal of Guangxi Normal University(Natural Science Edition), 2014, 32(3): 22-26.
[6] XU Gang, LIU Hai-yan, ZHANG Chao-ying, LIANG Zhen-yan. Simulations of Constructivism Application Based on Cellular Automata [J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(4): 7-12.
[7] DENG Min-yi, TAN Hui-li. The Qualitative Study for a Cellular Automata Model with Two Variables [J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(2): 1-6.
[8] YU Yan, BAI Ke-zhao, KONG Ling-jiang. Cellular Automaton Simulations of the Interactive Influence between Pedestrians and Vehicles [J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(1): 6-10.
[9] QIN Song, DENG Min-yi, KONG Ling-jiang. Simulation of Stock Market Influenced by Securities and Margin Financing Based on Cellular Automata [J]. Journal of Guangxi Normal University(Natural Science Edition), 2011, 29(4): 12-15.
[10] CHEN Yong-qi, BAI Ke-zhao, KUANG hua, KONG Ling-jiang, LIU Mu-ren. Effect of Internal Layout on the Pedestrian Evacuation in the Classroom [J]. Journal of Guangxi Normal University(Natural Science Edition), 2011, 29(1): 1-4.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!