On behavior of two-dimensional cellular automata with 
an exceptional rule under periodic boundary condition

doi:10.1016/S1005-8885(09)60426-X

中国邮电高校学报(英文) ›› 2010, Vol. 17 ›› Issue (1): 67-72.doi: 10.1016/S1005-8885(09)60426-X

• Artificial Intelligence • 上一篇下一篇

On behavior of two-dimensional cellular automata with
an exceptional rule under periodic boundary condition

翟莹,易忠,邓培民

Department of Mathematics, Guangxi Normal University, Guilin 541004, China

收稿日期:2009-03-30 修回日期:1900-01-01 出版日期:2010-02-28
通讯作者: 翟莹

On behavior of two-dimensional cellular automata with
an exceptional rule under periodic boundary condition

ZHAI Ying, YI Zhong, DENG Pei-min

Department of Mathematics, Guangxi Normal University, Guilin 541004, China

Received:2009-03-30 Revised:1900-01-01 Online:2010-02-28
Contact: ZHAI Ying

摘要/Abstract

摘要：

This article deals with the behavior of two-dimensional (2-D) cellular automata (CA) with a special rule under periodic boundary condition by using matrix algebra. The important characteristics of CA have been studied, such as Garden of Eden (GOE), maximal transient length, maximal cycle length and so forth. Several necessary and sufficient conditions are provided, which guarantee a given configuration of being a GOE in different cases. Besides, algorithms are proposed to obtain the number of GOEs, the maximal transient length, and the maximal cycle length in such a CA with the rule mentioned above under periodic condition.

关键词:

cellular;automata,;GOE,;maximal;transient;length,;maximal;cycle;length

Abstract:

Key words:

cellular automata;GOE;maximal transient length;maximal cycle length

ZHAI Ying, YI Zhong, DENG Pei-min. On behavior of two-dimensional cellular automata with
an exceptional rule under periodic boundary condition[J]. Acta Metallurgica Sinica(English letters), 2010, 17(1): 67-72.

参考文献

1. Von Neumann J. Theory of self-reproducing automata. Urbana, IL, USA: University of Illinois Press, 1966

2. Wolfram S. Statistical mechanics of cellular automata. Reviews of Modern Physics, 1983, 55 (3): 601-644

3. Laurio K, Linaker F, Narayanan A. Regular biosequence pattern matching with cellular automata. Information Science, 2002, 146 (1/2/3/4): 89-101

4. Lusth J C, Dixon B. A characterization of important algorithms for quantum-dot cellular automata. Information Science, 1999, 113(3/4): 193-204

5. Rubin S H. On randomization and discovery. Information Science, 2007, 177 (1): 170-191

6. Das A K. Additive cellular automata: theory and application as a built-in self-test structure. Kharagpur, India: Indian Institute of Technology Kharagpur, 1990

7. Inokuchi S. On behaviors of cellular automata with rule 156. Bulletin of Informatics and Cybernetics, 1998, 30 (1): 121-131

8. Akin H, Siap I. On cellular automata over Galois rings. Information Processing Letters, 2007, 103(1): 24-27

9. Jadur C, Yazlle J. On the dynamics of cellular automata induced from a prefix code. Advances in Applied Mathematics, 2007, 38(1): 27-53

10. Siap I, Akin H, Sah F. Characterization of two dimensional cellular automata over ternary fields. Proceedings of the 3rd International Conference on Modeling, Simulation and Applied Optimization (ICMSAO’09), Jan 22-24, 2009, Sharjah, United Arab Emirates. 2009: 22-24

11. Dihidar K, Choudhury P P. Matrix algebraic formulae concerning some exceptional rules of two-dimensional cellular automata. Information Science, 2004, 165(1/2): 91-101

12. Khan A R, Choudhury P P, Dihidar K, et al. VLSI architecture of a cellular automata. Computers and Mathematics with Applications, 1997, 33(5): 79-94

13. Khan A R, Choudhury P P, Dihidar K, et al. Text compression using two dimensional cellular automata. Computers and Mathematics with Applications, 1999, 37(6): 115-127

14. Zhai Y, Yi Z, Deng P M. On behavior of two-dimensional cellular automata with an exceptional rule. Information Science, 2009, 179(5): 613-622

15. Amoroso S, Cooper G, Patt Y N. Some clarification of the concept of a Garden-of-Eden configuration. Journal of Computer and System Sciences, 1975, 10: 77-82

16. Hopkins B, Sellers, J A. Exact enumeration of Garden of Eden partitions. INTEGERS: Electronic Journal of Combinational Number Theory, 2007, 7(2): 299-303

17. Stevens J G, Rosensweig R E, Cerkanowicz A E. Transient and cyclic behavior of cellular automata with null boundary conditions. Journal of Statistical Physics, 1993,73(1/2): 159-174

[1]	Xie Xiaoyan, Chai Miaomiao, Deng Junyong, Du Zhuolin, Yang Kun, Yin Shaorun. Hardware-friendly Cycle-GAN and reconfigurable design[J]. 中国邮电高校学报(英文版), 2023, 30(4): 10-20.
[2]	邓军勇吴皓月罗佳莹山蕊刘新闯. LOOKNoC: a low-loss, non-blocking, scalable passive optical interconnect network-on-chip architecture [J]. 中国邮电高校学报(英文版), 2021, 28(1): 94-106.
[3]	Pan Ziyu, Hu Han. Energy efficiency optimization for HCNs based on small base station transmission power allocation[J]. 中国邮电高校学报(英文版), 2020, 27(2): 19-25.
[4]	Li Bo, Sun Xuehong, Li Chunshu, Xue Kaiping, Zhang Xiaoguang. Downlink energy efficiency modeling and optimization with backhaul awareness and interference price in ultra cellular HetNet[J]. 中国邮电高校学报(英文版), 2019, 26(2): 67-81.
[5]	张志鹏陈增强刘忠信. Compatible-invariant subset analysis of deterministic finite automata via semi-tensor product of matrices approach[J]. 中国邮电高校学报(英文版), 2018, 25(5): 75-82.
[6]	陈瑞瑞张海林. Length minimization of uniform linear antenna array for millimeter wave communications with maximum capacity[J]. 中国邮电高校学报(英文版), 2017, 24(2): 96-102.
[7]	那飞迟学芬董雯于海凤. Jitter analysis of real-time services in IEEE 802.15.4 WSNs and wired IP concatenated networks[J]. 中国邮电高校学报(英文版), 2016, 23(4): 1-8.
[8]	曲志坚 Zhang Xianwei, Shi Shaojian, Cao Yanfeng, Zhao Mingbo. Network coding based all-optical multicast in WDM networks[J]. Acta Metallurgica Sinica(English letters), 2015, 22(1): 89-94.
[9]	牛勤曾志民张天魁 GAO Qiu-bin, SUN Shao-hui. Nash bargaining solution based multi-cell and multi-user interference alignment scheme for cellular networks[J]. Acta Metallurgica Sinica(English letters), 2014, 21(4): 1-7.
[10]	吴哲郭宇春陈常嘉. Online social network model with renewal and accelerated growth[J]. Acta Metallurgica Sinica(English letters), 2014, 21(4): 54-63.
[11]	陈磊李曦纪红刘刚. Load-balance cell association for improving network capacity in heterogeneous cellular networks[J]. Acta Metallurgica Sinica(English letters), 2014, 21(3): 56-62.
[12]	王永斌张鹤立李屹纪红. Joint resource allocation with QoS provisioning in K-tier heterogeneous cellular networks [J]. Acta Metallurgica Sinica(English letters), 2013, 20(4): 15-20.
[13]	陈守宁杨龙祥赵玉娟李璟. Impact of MAC frame length on energy efficiency in 6LowPAN[J]. Acta Metallurgica Sinica(English letters), 2013, 20(4): 67-72.
[14]	程荣 YAN Xiao-ming . Indoor multisource channel characteristic for visible light communication [J]. Acta Metallurgica Sinica(English letters), 2013, 20(4): 106-111.
[15]	杨卫东李攀刘燕朱红松. Adaptive TDMA slot assignment protocol for vehicular ad-hoc networks[J]. Acta Metallurgica Sinica(English letters), 2013, 20(1): 11-18.

On behavior of two-dimensional cellular automata with
an exceptional rule under periodic boundary condition

On behavior of two-dimensional cellular automata with
an exceptional rule under periodic boundary condition

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

On behavior of two-dimensional cellular automata with an exceptional rule under periodic boundary condition

On behavior of two-dimensional cellular automata with an exceptional rule under periodic boundary condition

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

On behavior of two-dimensional cellular automata with
an exceptional rule under periodic boundary condition

On behavior of two-dimensional cellular automata with
an exceptional rule under periodic boundary condition