CA符号动力学理论及其应用研究
|
摘要
由John von Neumann于1951年正式提出的细胞自动机(Cellular Automata,简称CA)是时间、空间和状态均离散的动力系统,充当着复杂系统良好的模拟工具.近年来,越来越多的科研工作者投入到CA的理论和应用研究之中.而在理论方面中,关于CA的分类问题始终是研究的热点课题.迄今为止,从多种不同角度分类CA的工作已非常之多,不过大多还是建立在预先给定的一些限制条件下,因此不具有一般性.本文从符号动力学角度出发,核心工作为讨论拓展情形下即由无穷个细胞组成的无边界条件限制的CA的全局等价分类问题,此外,其它主要工作还包括基本细胞自动机(Elementary Cellular Automta,简称ECA)的细胞神经网络(Cellular Neural Networks,简称CNN)实现及加性ECA规则的全局演化性质.具体来说,论文主要工作内容如下:
1.我们找出了两个由五个变量不同邻域组成的CNN基因(对应的输入输出布尔函数是线性可分的)成功实现了指纹特征图象中的端点和分支点的提取.这里值得一提的是,实际应用中的CNN基因对应的输入输出布尔函数必须是线性可分的.因此,对于由线性可分和线性不可分组成的ECA规则,我们分两步执行,第一步,直接用CNN基因实现线性可分的ECA规则.第二步,将线性不可分的ECA规则最优分解成线性可分的ECA规则的逻辑运算组合形式,再利用第一步的CNN基因实现.这样,所有的ECA规则都可以由CNN实现,某种程度上体现了ECA在CNN中的应用.
2.从符号动力学角度出发对由双边无穷个细胞组成的ECA进行了拓扑共轭分类.分类结果表明,由有限个细胞组成的周期边界条件下的ECA在拓展成双边无穷情形下的全局等价分类保持不变.进一步,我们发现用分类一般情形下的ECA的两个同胚映射同样适合分类一维半径为2的CA,加性规则的分类验证了这一点.在一维基础上,我们又对高维的一般情形下的CA给出了理论上拓扑共轭分类所需的同胚映射.特别地,利用这个平台,我们反过来寻找出了著名的生命游戏所对应的对偶规则.
3.源于Wolfram的在2002年出版的一类新科学(A New Kind of Science)一书中许多的模拟实验和经验观察结果,我们先回顾了从2002年到2007年Chua等人的系列论文的主要工作,而后讨论了ECA规则的Isle of Eden性质,简洁地证明了两个代表性加性ECA规则的一些全局演化性质.
Cellular automata (CA for short), formally introduced by John von Neumann in1951, are discrete (both in time, space and state) dynamical systems which serve asgood simulation tools for modeling many complex systems. In recent decades, moreand more researchers focus their attention on studying the theoretical and applied as-pects of CA. While in the field of theoretical research, the classification of CA is alwaysa hot topic, and heretofore many classification schemes have been presented from dif-ferent points of view. However, among them, the majority suffers the loss of generalitydue to many restricted conditions given under assumption. In this thesis, from the pointof view of symbolic dynamics, we investigate the extended CA which are composedof infinite number of cells without the restriction of boundary conditions, and the corework is to discuss the global equivalence classification. Moreover, other works includethe Cellular Neural Networks (CNN for short) realizations of Elementary Cellular Au-tomata (ECA for short) and global evolutionary properties of some additive ECA rules.More specifically, the main contents of this thesis are as follows:
1. We find, in this thesis, two CNN genes (corresponding input-output Booleanfunctions are linearly separable) composed of five variables with two kinds ofneighborhoods to successfully extract the endings and bifurcation points in theprintfeature image. Noteworthy, the input-output Boolean function correspond-ing the CNN gene in practice should be linearly separable. In terms of ECAcomposed of both linear separable and linear non-separable rules, we thereforeoperate by two steps. First step, we directly implement linear separable ECArules via CNN genes, and second step, we optimally decompose the linear non-separable ECA rules into the logic operation combinations of linear separableECA rules, then utilize the CNN genes obtained in the first step to implementthem. In this sense we implement all ECA rules, which to some extent re?ectsthe ECA application in CNN.
2. We present a topological conjugacy classification of ECA composed of bi-infinitenumber of cells from the point of view of symbolic dynamics, and the classifica-tion result coincides with that of ECA composed of finite number of cells withperiodic boundary conditions. Furthermore, we find that the two homeomor-phisms which are utilized to classify ECA in the extended case can also be usedto group one-dimensional CA with radius 2. The classification of additive rules validates the result. On the foundation of one-dimensional cases, we also pro-vide theoretically the homeomorphisms that classify high-dimensional CA in anextended case. Particularly, we find the dual rule of the famous game of life rulebasing on this platform.
3. In light of many results obtained by Wolfram through large amount of computersimulations and empirical observations in A New Kind of Science published in2002, we firstly recap the main results in paper series conducted by Chua et alfrom 2002 to 2007, then we investigate some properties of Isle of Eden possessedby some ECA rules. We also give a simple proof of some global evolutionaryproperties of two representative additive ECA rules.
1.我们找出了两个由五个变量不同邻域组成的CNN基因(对应的输入输出布尔函数是线性可分的)成功实现了指纹特征图象中的端点和分支点的提取.这里值得一提的是,实际应用中的CNN基因对应的输入输出布尔函数必须是线性可分的.因此,对于由线性可分和线性不可分组成的ECA规则,我们分两步执行,第一步,直接用CNN基因实现线性可分的ECA规则.第二步,将线性不可分的ECA规则最优分解成线性可分的ECA规则的逻辑运算组合形式,再利用第一步的CNN基因实现.这样,所有的ECA规则都可以由CNN实现,某种程度上体现了ECA在CNN中的应用.
2.从符号动力学角度出发对由双边无穷个细胞组成的ECA进行了拓扑共轭分类.分类结果表明,由有限个细胞组成的周期边界条件下的ECA在拓展成双边无穷情形下的全局等价分类保持不变.进一步,我们发现用分类一般情形下的ECA的两个同胚映射同样适合分类一维半径为2的CA,加性规则的分类验证了这一点.在一维基础上,我们又对高维的一般情形下的CA给出了理论上拓扑共轭分类所需的同胚映射.特别地,利用这个平台,我们反过来寻找出了著名的生命游戏所对应的对偶规则.
3.源于Wolfram的在2002年出版的一类新科学(A New Kind of Science)一书中许多的模拟实验和经验观察结果,我们先回顾了从2002年到2007年Chua等人的系列论文的主要工作,而后讨论了ECA规则的Isle of Eden性质,简洁地证明了两个代表性加性ECA规则的一些全局演化性质.
Cellular automata (CA for short), formally introduced by John von Neumann in1951, are discrete (both in time, space and state) dynamical systems which serve asgood simulation tools for modeling many complex systems. In recent decades, moreand more researchers focus their attention on studying the theoretical and applied as-pects of CA. While in the field of theoretical research, the classification of CA is alwaysa hot topic, and heretofore many classification schemes have been presented from dif-ferent points of view. However, among them, the majority suffers the loss of generalitydue to many restricted conditions given under assumption. In this thesis, from the pointof view of symbolic dynamics, we investigate the extended CA which are composedof infinite number of cells without the restriction of boundary conditions, and the corework is to discuss the global equivalence classification. Moreover, other works includethe Cellular Neural Networks (CNN for short) realizations of Elementary Cellular Au-tomata (ECA for short) and global evolutionary properties of some additive ECA rules.More specifically, the main contents of this thesis are as follows:
1. We find, in this thesis, two CNN genes (corresponding input-output Booleanfunctions are linearly separable) composed of five variables with two kinds ofneighborhoods to successfully extract the endings and bifurcation points in theprintfeature image. Noteworthy, the input-output Boolean function correspond-ing the CNN gene in practice should be linearly separable. In terms of ECAcomposed of both linear separable and linear non-separable rules, we thereforeoperate by two steps. First step, we directly implement linear separable ECArules via CNN genes, and second step, we optimally decompose the linear non-separable ECA rules into the logic operation combinations of linear separableECA rules, then utilize the CNN genes obtained in the first step to implementthem. In this sense we implement all ECA rules, which to some extent re?ectsthe ECA application in CNN.
2. We present a topological conjugacy classification of ECA composed of bi-infinitenumber of cells from the point of view of symbolic dynamics, and the classifica-tion result coincides with that of ECA composed of finite number of cells withperiodic boundary conditions. Furthermore, we find that the two homeomor-phisms which are utilized to classify ECA in the extended case can also be usedto group one-dimensional CA with radius 2. The classification of additive rules validates the result. On the foundation of one-dimensional cases, we also pro-vide theoretically the homeomorphisms that classify high-dimensional CA in anextended case. Particularly, we find the dual rule of the famous game of life rulebasing on this platform.
3. In light of many results obtained by Wolfram through large amount of computersimulations and empirical observations in A New Kind of Science published in2002, we firstly recap the main results in paper series conducted by Chua et alfrom 2002 to 2007, then we investigate some properties of Isle of Eden possessedby some ECA rules. We also give a simple proof of some global evolutionaryproperties of two representative additive ECA rules.
引文
[1] M. Davis. A note on universal Turing machines. Princeton University Press, Princeton, NJ,1956.
[2] M. Davis. The definition of universal turing machines. Proc. Am. Math. Soc., 8:1125–1126,1957.
[3] A. Hodges. Alan Turing: Mathematician and Computer Builder. New Scientist, 1983.
[4] J.V. Neumann. Theory of Self-Reproducing Automata(ed. by Burks, A.W.). University ofIllinois, Urbana, 1966.
[5] A.W. Burks. Von Neumann’s self-reproducing automata. University of Illinois Press, Cham-paign, IL, 1970.
[6] E.F. Codd. Celluar Automata. Academic Press, New York, 1968.
[7] G.A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Mathe-matical Systems Theory, 3:320–375, 1969.
[8] M. Gardner. On Celluar Automata, Self-Reproduction, the Garden of Eden, and the Game ofLife. Scientific American, 1971.
[9] L.S. Schulman and P.E. Seiden. Statistical mechanics of a dynamical system based on con-way’s game of life. J. Stat Phys., 19:293, 1978.
[10] E.R. Berlekamp, J.H. Conway, and R. Guy. Winning Ways for your Mathematical Plays.Academic Press, 1982.
[11] T. Toffoli. Computation and construction universality of reversible cellular automata. Journalof Computer and System Sciences, 15:213–231, 1977.
[12] J. D. Farmer, T. Toffoli, and S. Wolfram. Cellular automata. North-Holland, Amsterdam,1984.
[13] T. Toffoli and N. Margolus. Invertible cellular automata: A review. Physica D, 45:229, 1990.
[14] S. Wolfram. Statistical mechanics of cellular automata. Rev. Mod. Phys., 55:601–644, 1983.
[15] S. Wolfram. Twenty problems in the theory of cellular automata. Physica Scripta, 9:1–35,1985.
[16] O. Martin, A.M. Odlyzko, and S. Wolfram. Algebraic properties of cellular automata. Com-mun. Math. Phys., 93:219–258, 1984.
[17] S. Wolfram. Random sequence generation by cellular automata. Adv. Appl. Math, 7:123–169,1986.
[18] S. Wolfram. Computation theory of cellular automata. Communications in MathematicalPhysics, 96:15–57, 1984.
[19] S. Wolfram. University and complexity in cellular automata. Physica D, 10:1–35, 1984.
[20] S. Wolfram. undecidability and intractability in physics. Phys. Rev. Lett., 54:735, 1985.
[21] S. Wolfram. Theory and Applications of Cellular Automata. World Scientific, Singapore,1986. ISBN 9971-50-124-4 pbk.
[22] S. Wolfram. Celluar automata ?uids: basic theory. J. Statist. Phys., 45:471–526, 1986.
[23] E. Fredkin. Digital mechanics: An informational process based on reversible universal CA.Physica D, 45:254, 1990.
[24] K. Culik II, L.P. Hurd, and S Yu. Computation theoretic aspects of cellular automata. PhysicaD, 45:357–378, 1990.
[25] D. Stauffer. Computer simulation of cellular automata. J. Phys. A: Math. Gen., 24:909–927,1991.
[26] D. Stauffer and R. Pandey. Immunologically motivated simulation of cellular automata. Com-puters in Physics, 6:4:404–410, 1992.
[27] K. Eloranta. Random walks in cellular automata. Nonlinearity, 6:1025–1036, 1993.
[28] J. Kari. Rice’s theorem for the limit set of cellular automata. Theoretical Computer Science,127:229–254, 1994.
[29] S. Takesue. Staggered invariants in cellular automata. Complex Syst., 9:149–168, 1995.
[30] B. Voorhees. Computational Analysis of One-Dimensional Celluar Automata. World Scien-tific, 1996.
[31] H. Bussemaker, A. Deutsch, and E. Geigant. Mean-field analysis of a dynamical phasetransition in a cellular automaton model for collective motion. Phys. Rev. Lett., 78:5018–5021, 1997.
[32] B. Chopart and M. Droz. Celluar Automata Modeling of Physical Systems. CambridgeUniversity Press, Cambridge, 1998.
[33] K. Sutner. Linear cellular automata and de bruijin automata. Mathematics and its Applica-tions, 460:303–320, 1999.
[34] T. Toffoli and N. Margolus. Injective cellular automata. Physica D, 45:386–395, 1990.
[35] M. Hurley. Attractors in cellular automata. Ergodic Theory & Dynamic system, 10:131–140,1990.
[36] H.B. Sieburg and O.K. Clay. Cellular automata as algebraic systems. Complex Syst., 5:575–602, 1991.
[37] M.A. Shereshevsky. Ergodic properties of certain surjective cellular automata. Mh. Math,114:305–316, 1992.
[38] M.A. Shereshevsky. Expansiveness, entropy and polynomial growth for groups acting onsubshifts by automorphisms. Indag. Math. N.S., 4:203–210, 1993.
[39] J. Kari. Reversibility and surjectivity of cellular automata. J. Comput. System Sci., 48:149–182, 1994.
[40] A. Maass. On sofic limit sets of cellular automata. Ergodic Theory and Dynamical Systems,15:663–684, 1995.
[41] S. Chakraborty, D. Roy Chowdhury, and P. Pal Chaudhuri. Theory and applications of non-group cellular automata for synthesis of easily testable finite state machines. IEEE Trans. onComputers, 45:769–781, 1996.
[42] P. Favati, G. Lotti, and L. Margara. One dimensional additive cellular automata and chaoticaccording to devaney’s definition of chaos. Theoretical Computer Science, 174:157–170,1997.
[43] G. Manzini and L. Margara. Invertible linear cellular automata over zm: algorithmic anddynamical aspects. J. Comput. System Sci., 56:60–67, 1998.
[44] G. Manzini. Attractors of linear cellular automata. Journal of Computer and System Sciences,58:597–610, 1999.
[45] A. Ilachinski. Cellular Automata: A Discrete Universe. World Scientific, 2001.
[46] S. Wolfram. A New Kind of Science. Wolfram Media., Inc., 2002.
[47] G.B. Ermentrout. Featured review: A new kind of science. SIAM Rev., 45:361–365, 2003.
[48] L. Gray. A mathematican looks at Wolfram’s New Kind of Science. Notices of the AMS,50:200–211, 2003.
[49] L.O. Chua, S. Yoon, and R. Dogaru. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part I: Threshold of complexity. Int. J. Bifurcation Chaos, 12:2655–2766,2002.
[50] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part II: Universal neuron. Int. J. Bifurcation Chaos, 13:2377–2491, 2003.
[51] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part III: Predicting the unpredictable. Int. J. Bifurcation Chaos, 14:3689–3820, 2004.
[52] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science.Part IV: From bernoulli shift to 1/f spectrum. Int. J. Bifurcation Chaos,15:1045–1183, 2005.
[53] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part V: Fractals everywhere. Int. J. Bifurcation Chaos, 15:3701–3849, 2005.
[54] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part VI: From time-reversible attractors to the arrow of time. Int. J. Bifurca-tion Chaos, 16:1097–1373, 2006.
[55] L.O. Chua, J. Guan, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wol-fram’s new kind of science. Part VII: Isles of Eden. Int. J. Bifurcation Chaos, 17:2839–3012,2007.
[56] L.O. Chua, K. Karacs, V.I. Sbitnev, J. Guan, and S. Yook. A nonlinear dynamics perspectiveof Wolfram’s new kind of science. Part VIII: More Isles of Eden. Int. J. Bifurcation Chaos,17:3741–3894, 2007.
[57] L.O. Chua. A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Science, Volume I.World Scientific, Singapore, 2006.
[58] L.O. Chua. A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Science, VolumeII. World Scientific, Singapore, 2007.
[59] P. Hogeweg. Cellular automata as a paradigm for ecological modeling. Applied Mathematicsand Computation, 27:81–100, 1988.
[60] P. Manneville, N. Boccara, G. Vichniac, and R. Bidaux. Cellular automata and the modelingof complex physical systems. Springer, Berlin, 1989.
[61] H. Baltzer, W.P. Braun, and W. Kohler. Celluar automata model for vegetable dynamics.Ecological Modelling, 107:113–125, 1998.
[62] R.M. Zorzenon, dos Santos and S. Coutinho. Dynamics of HIV infection: A cellular au-tomata approach. Phys. Rev. Lett., 87:168102, 2001.
[63] G. Qiu, D. Kandhai, and P.M.A. Sloot. Understanding the complex dynamics of stock mar-kets through cellular automata. Phys. Rev. E, 75:046116, 2007.
[64] S. Raghavan and S.S. Sahay. Modeling the grain growth kinetics by cellular automaton.Materials Science and Engineering, 445-446:203–209, 2007.
[65] W. Yuan and K.H. Tan. An evacuation model using cellular automata. Physica A, 384:549–566, 2007.
[66] K. Culik II and S Yu. Undecidability of ca classification schemes. Complex Systems, 2:177–190, 1988.
[67] K. Culik II, J Pachl, and S Yu. On the limit sets of cellular automata. SIAM J. Comput.,18(4):831, 1989.
[68] T.E. Ingerson and R.L. Buvel. Structure in asynchronous cellular automata. Physica D,10:59–68, 1984.
[69] F. Bagnoli, N. Boccara, and R. Rechtman. Nature of phase transitions in probabilistic cellularautomata with two absorbing states. Lect. Notes Comput. Sci., 2493:249–258, 2002.
[70] S.A. Billings and Y. Yang. Identification of probabilistic cellular automata. IEEE Transac-tions on Systems, Man and Cybernetics, 33:225–236, 2003.
[71] G. Grinstein, C. Jayaprakash, and Y. He. Statistical mechanics of probabilistic cellular au-tomata. Phys. Rev. Lett, 55:2527–2530, 1985.
[72] W. Just. Phase transitions in coupled map lattices and in associated probabilistic cellularautomata. Phys. Rev. E, 74:046209, 2006.
[73] K. Kaneko. Spatiotemporal intermittency in coupled map lattices. Prog. of Theo. Phy.,74:1033–1044, 1985.
[74] J.T. Dockery and A.E.R. Woodcock. The Military Landscape: Mathematical Models ofCombat. Cambridge, England: Woodhead Publishing Limited, 1993.
[75] S.A Kauffman. Emergent properties in random complex systems. Physica D, 10:146–156,1984.
[76] P. Halpern. Sticks and stones: a guide to structurally dynamic cellular automata. AmericanJournal of Physics, 57(5):405–408, May 1989.
[77] P. Halpern and G. Caltagirone. Behavior of topological cellular automata. Complex Syst.,4:623–651, 1990.
[78] G. Grossing and A. Zeilinger. Quantum cellular automata. Complex Syst., 2:197–208, 1988.
[79] M. Khatun, T. Barclay, I. Sturzu, and P.D. Tougaw. Fault tolerance properties in quantum-dotcellular automata devices. J. Phys. D: Appl. Phys., 39:1489–1494, 2006.
[80] A. Kay. Unifying quantum state transfer and state amplification. Phy. Rev. Lett., 98:010501,2007.
[81] B.F. Madore and W.L. Freedman. Computer simulations of the Belousov-Zhabotinsky reac-tion. Science, 222:615–616, 1983.
[82] R. Durrett and J. E. Steif. Some rigorous results for the Greenberg-Hastings model. Journalof Theoretical Probability, 4:669–690, 1991.
[83] J.M. Greenberg, B.D. Hassard, and S.P. Hastings. Pattern formation and periodic structuresin systems modelled by reaction-diffusion equations. Bulletin of the American MathematicalSociety, 84:1296–1327, 1978.
[84] J.M. Greenberg and S.P. Hastings. Spatial patterns for discrete models of diffusion in ex-citable media. SIAM Journal on Applied Mathematics, 34:515–523, 1978.
[85] J.M. Greenberg, C. Greene, and S. Hastings. A combinatorial problem arising in the study ofreaction-diffusion equations. SIAM Journal of Algebra and Discrete Mathematics, 1:34–42,1980.
[86] F. Blanchard, E. Formenti, and P. Ku?rka. Celluar automata in the cantor, besicovitch andweyl topological spaces. Complex Syst., 11:107–123, 1999.
[87] E. Formenti. On the sensitivity of additive cellular automata in besicovitch topologies. The-oret. Comput. Sci., 301:341–354, 2003.
[88] N. Romero, A. Rovella, and F. Vilamajo′. Remark on cellular automata and shift preservingmaps. Applied Mathematics Letters, 19:576–580, 2006.
[89] N. Chomsky. Three models for the description of language. IRE Trans. Info. Theo., IT2:113–129, 1956.
[90] P. Ku?rka. Languages, equicontinuity and attractors in cellular automata. Ergodic Theory &Dynamic system, 17:417–433, 1997.
[91] P. Ku?rka. Celluar automata with an infinite number of subshift attractors. Complex Systems,17:219–230, 2007.
[92] H. Umeo. Linear-time recognition of connectivity of binary images on 1-bit inter-cell com-munication cellular automaton. Parallel Computing, 27:587–599, 2001.
[93] J.L. Cardenas-Barrera, K.N. Plataniotis, and A.N. Venetsanopoulos. QCA implementation ofa multichannel filter for image processing. Mathematical Problems in Engineering, 8:87–99,2002.
[94] R.J. Chen and J.L. Lai. Image security system using recursive cellular automata substitution.Pattern Recognition, 40:1621–1631, 2007.
[95] K. Nagel and M. Shreckenberg. A cellular automaton model for freeway traffic. J. Phys. I.France, 2:2221–2229, 1992.
[96] M. Fukui and Y. Ishibashi. Traffic ?ow in 1D cellular automaton model including cars mov-ing with high speed. J. Phys. Soc. Japan, 65:1868–1870, 1996.
[97] E.G. Camparil and G. Levi. A cellular automata model for highway traffic. Eur. Phys. J. B,17:159–166, 2000.
[98] J. Wahle, L. Neubert, J. Esser, and M. Schreckenberg. A cellular automaton traffic ?owmodel for online simulation of traffic. Parallel Computing, 27:719–735, 2001.
[99] N. Moussa. Car accidents in cellular automata models for one-lane traffic ?ow. Phys. Rev.E, 68:036127, 2003.
[100] X.Q. Yang, W. Zhang, K. Qiu, W.T. Xu, G. Tang, and L. Ren. The relations of“go andstop”wave to car accidents in a cellular automaton with velocity-dependent randomization.Physica A, 384:589–599, 2007.
[101] D.G. Green. Cellular automata models in biology. Mathematical and Computer Modelling,13:69–74, 1990.
[102] G. Bard Ermentrout and Leah Edelstein-Keshet. Cellular automata approaches to biologicalmodeling. Journal of Theoretical Biology, 160:97–133, Jan 1993.
[103] C. Salzberg, A. Antony, and H. Sayama. Evolutionary dynamics of cellular automata-basedself-replicators in hostile environments. Biosystems, 78:119–134, 2004.
[104] R.D. Handy. Systems toxicology: using the systems biology approach to assess chemicalpollutants in the environment. Advances in Experimental Biology, 2:249–281, 2008.
[105] S. Wolfram. Cryptography with cellular automata. In Advances in Cryptology: Crypto’85Proceedings, Lecture Notes in Computer Science, 218 (Springer-Verlag) 429-432, 1986.
[106] D.R. Chowdhury, L.S. Gupta, and P.P. Chaudhuri. A class of two-dimensional cellular au-tomata and applications in random pattern testing. Journal of Electronic Testing: Theory andApplication, 5:65–80, 1994.
[107] M. Tomassini, M. Sipper, and M. Perrenoud. On the generation of high-quality randomnumbers by two-dimensional cellular automata. IEEE Transactions on Computers, 49:1146–1151, 2000.
[108] M. Tomassini and M. Perrenoud. Cryptography with cellular automata. Applied Soft Com-puting, 1:151–160, 2001.
[109] F. Seredynski, P. Bouvry, and A.Y. Zomaya. Celluar automata computations and secret keycryptography. Parallel Computing, 30:753–766, 2004.
[110] J. Sung, D. Hong, and S. Hong. Cryptanalysis of an involutional block cipher using cellularautomata. Information Processing Letters, 104:183–185, 2007.
[111] L.Z. Guo and S.A. Billings. Identification of binary cellular automata from spatio-temporalbinary patterns using a fourier representation. Int. J. Bifurcation Chaos, 17:1985–1996, 2007.
[112] A. Shreim, P. Grassberger, W. Nadler, B. Samuelsson, J. Socolar, and M. Paczuski. Networkanalysis of the state space of discrete dynamical systems. Phys. Rev. Lett., 98:198701, 2007.
[113] S. Adachi, J. Lee, F. Peper, and H. Umeo. Kaleidoscope of Life: A 24-neighbourhood outer-totalistic cellular automaton. Physica D, 237:800–817, 2008.
[114] J.Y. Ko, Y.C. Hung, M.C. Ho, and I.M. Jiang. Chaotic behavior in the disorder cellularautomata. Chaos, Solitons & Fractals, 36:934–939, 2008.
[115] J.R. Sa′nchez and R. Lo′pez-Ruiz. Symmetry pattern transition in cellular automata withcomplex behavior. Chaos, Solitons & Fractals, 37:638–642, 2008.
[116] A.R. Mikler, S. Venkatachalam, and K. Abbas. Modeling infiectious diseases using globalstochastic cellular automata. Journal of Biological Systems, 13:421–439, 2005.
[117] A.H. Encinas, L.H. Encinas, S.H. White, A.M. del Rey, and G.R. Sanchez. Simulation offorest fire fronts using cellular automata. Advances in Engineering Software, 38:372–378,2007.
[118] H. Yue, H. Hao, Y. Chen, and C. Shao. Simulation of pedestrian ?ow on square lattice basedon cellular automata model. Physica A, 384:567–588, 2007.
[119] I.G. Georgoudas, G.C. Sirakoulis, E.M. Scordilis, and I. Andreadis. A cellular automatonsimulation tool for modelling seismicity in the region of Xanthi. Environmental Modelling& Software, 22:1455–1464, 2007.
[120] M. Bartolozzi and A.W. Thomas. Stochastic cellular automata model for stock market dy-namics. Phys. Rev. E, 69:046112, 2004.
[121] P. Ku?rka. On the measure attractors of a cellular automaton. Discrete and Continuous Dy-namical Systems, Supplement Volume:524–535, 2005.
[122] E. Formenti and P. Ku?rka. Subshift attractors of cellular automata. Nonlinearity, 20:1–13,2007.
[123] A. Wuensche and M. Lesser. The Global Dynamics of Cellular Automata. Addision-Wesley,Reading, MA, 1992.
[124] L.O. Chua and L. Yang. Cellular neural networks: Theory. IEEE Trans. Circuits Syst.,35:1257–1272, 1988.
[125] L.O. Chua and L. Yang. Cellular neural networks: Applications. IEEE Trans. Circuits Syst.,35:1273–1290, 1988.
[126] J.M. Cruz and L.O. Chua. A cnn chip for connected component detection. IEEE Trans.Circuits Syst., 38:812–817, 1991.
[127] L.O. Chua, L. Yang, and K.R. Krieg. Signal processing using cellular neural networks.Journal of VLSI Signal Processing, 3:25–51, 1991.
[128] P. Szolgay, Vo¨ro¨s, and G. Ero¨ss. On the applications of the cellular neural network paradigmin mechanical vibrating systems. IEEE Trans. Circuits Syst. I: Fundamental Theory andApplications, 40:222–227, 1993.
[129] L.O. Chua, M. Hasler, G.S. Moschytz, and J. Neirynck. Autonomous cellular neural net-works: A unified paradigm for pattern formation and active wave propagation. IEEE Trans.Circuits Syst., 42:559–577, 1995.
[130] P. Arena, L. Fortuna, M. Frasca, and Patane′. A CNN-based chip for robot locomotion control.IEEE Trans. Circuits Syst.I: Regular Papers, 52:1862–1871, 2005.
[131] H. Aomori, T. Otake, N. Takahashi, and M. Tanaka. Sigma-delta cellular neural network for2D modulation. Neural Networks, 2008 Special Issue, 21:349–357, 2008.
[132] J.M. Cruz and L.O. Chua. A 16×16 cellular neural network universal chip: the first completesingle-chip dynamic computer array with distributed memory and with gray-scale input-output. Analog Integr. Circuits Sig. Process. J., 15:227–238, 1998.
[133] L.O. Chua and T. Roska. Celluar Neural Networks—Foundations and Primer. LectureNotes/EE129, University of California, Berkeley, 1997.
[134] L.O. Chua. CNN: A Paradigm for Complexity. World Scientific, Singapore, 1998.
[135] G. Qun, F. Philipp, R.M. Karl, and S.M. Geore. Fingerprint recognition using CNNs: Fin-gerprint preprocessing. In Proc. IEEE Int. Symp. Circuits and Systems(ISCAS2001), Sydney,Australia, volume 3, pages 433–436, 2001.
[136] Y. Lou, F. Chen, and J. Guan. Fingerprint feature extraction via CNN with von Neumannneighborhood. Int. J. Bifurcation Chaos, 17:4145–4151, 2007.
[137] F.Y. Chen, G.L. He, and G.R. Chen. Realization of Boolean functions via CNN with vonNeumann neighborhood. Int. J. Bifurcation Chaos, 16:1389–1403, 2006.
[138] M. Cook. Universality in elementary cellular automata. Complex Syst., 15:1–40, 2004.
[139] L.O. Chua and T. Roska. Celluar Neural Networks and Visual Computing: Foundations andApplications. Cambridge University Press, Cambridge, 2002.
[140] F.Y. Chen and G. Chen. Realization and bifurcation of boolean functions via cellular neuralnetworks. Int. J. Bifurcation Chaos, 15:2109–2129, 2005.
[141] P.M. Binder. Topological classification of cellular automata. J. Phys. A.: Math. Gen.,24:L31–L34, 1991.
[142] R. Badii and A. Politi. Thermodynamics and complexity of cellular automata. Phys. Rev.Lett., 78(3):444–447, 1997.
[143] D. Feldman and J. Crutchfield. Measures of statistical complexity: why. Phys. Lett. A,238:244–252, 1998.
[144] S. Sakai, M. Kanno, and Y. Saito. Quiescent string dominance parameter f and classificationof one-dimensional cellular automata. Phys. Rev. E, 69:066117, 2004.
[145] S. Wiggins. Introduction to Applied Nonlinear Dynamical Systems and Chaos(second edi-tion). Springer-Verlag, Berlin, NY, 2003.
[146] R. Alonso-Sanz. One-dimensional r=2 cellular automata with memory. Int. J. Bifurcationand Chaos, 14:3217–3248, 2004.
[147] J. Freire and J. Gallas. Synchronization and predictability under rule 52, a cellular automatonreputedly of class 4. Physics Letters A, 366:25–29, 2007.
[148] G. Cattnaneo, M. Finelli, and L. Margara. Investigating topological chaos by elementarycellular automata dynamics. Theoretical Computer Science, 244:219–241, 2000.
[149] M.S. Capcarrere, M. Sipper, and M. Tomassini. Two-state, r=1 cellular automaton that clas-sifies density. Phy. Rev. Lett., 77:4969–4971, 1996.
[150] D. A. Lind. Applications of ergodic theory and sofic systems to cellular automata. PhysicaD, 10:36–44, 1984.
[151] J.E. Hanson and J. Crutchfield. The attractor-basin portrait of a cellular automaton. Journalof Statistical Physics, 66:1415–1462, 1992.
[152] G. Cattnaneo, E. Formenti, G. Manzini, and L. Margara. Ergodicity, transitivity, and regular-ity for linear cellular automata over Zm. Theort. Comput. Sci., 233:147–164, 2000.
[153] H. Akin. On the ergodic properties of certain additive cellular automata over Zm. AppliedMathematics and Computation, 168:192–197, 2005.
[154] J. Milnor. On the entropy geometry of cellular automata. Complex Syst., 2:357–386, 1988.
[155] L.P. Hurd, J. Kari, and K. Culik. The topological entropy of cellular automata is uncom-putable. Ergodic Theory and Dynamical Systems, 12:255–265, 1992.
[156] M.A. Shereshevsky. Lyapunov exponents for one-dimensional cellular automata. J. Nonlin-ear Sci., 2:1–8, 1992.
[157] M. Finelli, G. Manzini, and L. Margara. Lyapunov exponents vs expansivity and sensitivityin cellular automata. J. Complexity, 14:210–233, 1998.
[158] P. Tisseur. Celluar automata and Lyapunov exponents. Nonlinearity, 13:1547–1560, 2000.
[159] M. Courbage and Kamin′ski. Space-time directional Lyapunov exponents for cellular au-tomata. Jour. Stat. Physics, 124:1499–1509, 2006.
[160] R. Dogaru and L.O. Chua. Cnn genes for one-dimensional cellular automata: A multi-nestedpiecewise-linear approach. Int. J. Bifurcation Chaos, 8:1987–2001, 1998.
[2] M. Davis. The definition of universal turing machines. Proc. Am. Math. Soc., 8:1125–1126,1957.
[3] A. Hodges. Alan Turing: Mathematician and Computer Builder. New Scientist, 1983.
[4] J.V. Neumann. Theory of Self-Reproducing Automata(ed. by Burks, A.W.). University ofIllinois, Urbana, 1966.
[5] A.W. Burks. Von Neumann’s self-reproducing automata. University of Illinois Press, Cham-paign, IL, 1970.
[6] E.F. Codd. Celluar Automata. Academic Press, New York, 1968.
[7] G.A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Mathe-matical Systems Theory, 3:320–375, 1969.
[8] M. Gardner. On Celluar Automata, Self-Reproduction, the Garden of Eden, and the Game ofLife. Scientific American, 1971.
[9] L.S. Schulman and P.E. Seiden. Statistical mechanics of a dynamical system based on con-way’s game of life. J. Stat Phys., 19:293, 1978.
[10] E.R. Berlekamp, J.H. Conway, and R. Guy. Winning Ways for your Mathematical Plays.Academic Press, 1982.
[11] T. Toffoli. Computation and construction universality of reversible cellular automata. Journalof Computer and System Sciences, 15:213–231, 1977.
[12] J. D. Farmer, T. Toffoli, and S. Wolfram. Cellular automata. North-Holland, Amsterdam,1984.
[13] T. Toffoli and N. Margolus. Invertible cellular automata: A review. Physica D, 45:229, 1990.
[14] S. Wolfram. Statistical mechanics of cellular automata. Rev. Mod. Phys., 55:601–644, 1983.
[15] S. Wolfram. Twenty problems in the theory of cellular automata. Physica Scripta, 9:1–35,1985.
[16] O. Martin, A.M. Odlyzko, and S. Wolfram. Algebraic properties of cellular automata. Com-mun. Math. Phys., 93:219–258, 1984.
[17] S. Wolfram. Random sequence generation by cellular automata. Adv. Appl. Math, 7:123–169,1986.
[18] S. Wolfram. Computation theory of cellular automata. Communications in MathematicalPhysics, 96:15–57, 1984.
[19] S. Wolfram. University and complexity in cellular automata. Physica D, 10:1–35, 1984.
[20] S. Wolfram. undecidability and intractability in physics. Phys. Rev. Lett., 54:735, 1985.
[21] S. Wolfram. Theory and Applications of Cellular Automata. World Scientific, Singapore,1986. ISBN 9971-50-124-4 pbk.
[22] S. Wolfram. Celluar automata ?uids: basic theory. J. Statist. Phys., 45:471–526, 1986.
[23] E. Fredkin. Digital mechanics: An informational process based on reversible universal CA.Physica D, 45:254, 1990.
[24] K. Culik II, L.P. Hurd, and S Yu. Computation theoretic aspects of cellular automata. PhysicaD, 45:357–378, 1990.
[25] D. Stauffer. Computer simulation of cellular automata. J. Phys. A: Math. Gen., 24:909–927,1991.
[26] D. Stauffer and R. Pandey. Immunologically motivated simulation of cellular automata. Com-puters in Physics, 6:4:404–410, 1992.
[27] K. Eloranta. Random walks in cellular automata. Nonlinearity, 6:1025–1036, 1993.
[28] J. Kari. Rice’s theorem for the limit set of cellular automata. Theoretical Computer Science,127:229–254, 1994.
[29] S. Takesue. Staggered invariants in cellular automata. Complex Syst., 9:149–168, 1995.
[30] B. Voorhees. Computational Analysis of One-Dimensional Celluar Automata. World Scien-tific, 1996.
[31] H. Bussemaker, A. Deutsch, and E. Geigant. Mean-field analysis of a dynamical phasetransition in a cellular automaton model for collective motion. Phys. Rev. Lett., 78:5018–5021, 1997.
[32] B. Chopart and M. Droz. Celluar Automata Modeling of Physical Systems. CambridgeUniversity Press, Cambridge, 1998.
[33] K. Sutner. Linear cellular automata and de bruijin automata. Mathematics and its Applica-tions, 460:303–320, 1999.
[34] T. Toffoli and N. Margolus. Injective cellular automata. Physica D, 45:386–395, 1990.
[35] M. Hurley. Attractors in cellular automata. Ergodic Theory & Dynamic system, 10:131–140,1990.
[36] H.B. Sieburg and O.K. Clay. Cellular automata as algebraic systems. Complex Syst., 5:575–602, 1991.
[37] M.A. Shereshevsky. Ergodic properties of certain surjective cellular automata. Mh. Math,114:305–316, 1992.
[38] M.A. Shereshevsky. Expansiveness, entropy and polynomial growth for groups acting onsubshifts by automorphisms. Indag. Math. N.S., 4:203–210, 1993.
[39] J. Kari. Reversibility and surjectivity of cellular automata. J. Comput. System Sci., 48:149–182, 1994.
[40] A. Maass. On sofic limit sets of cellular automata. Ergodic Theory and Dynamical Systems,15:663–684, 1995.
[41] S. Chakraborty, D. Roy Chowdhury, and P. Pal Chaudhuri. Theory and applications of non-group cellular automata for synthesis of easily testable finite state machines. IEEE Trans. onComputers, 45:769–781, 1996.
[42] P. Favati, G. Lotti, and L. Margara. One dimensional additive cellular automata and chaoticaccording to devaney’s definition of chaos. Theoretical Computer Science, 174:157–170,1997.
[43] G. Manzini and L. Margara. Invertible linear cellular automata over zm: algorithmic anddynamical aspects. J. Comput. System Sci., 56:60–67, 1998.
[44] G. Manzini. Attractors of linear cellular automata. Journal of Computer and System Sciences,58:597–610, 1999.
[45] A. Ilachinski. Cellular Automata: A Discrete Universe. World Scientific, 2001.
[46] S. Wolfram. A New Kind of Science. Wolfram Media., Inc., 2002.
[47] G.B. Ermentrout. Featured review: A new kind of science. SIAM Rev., 45:361–365, 2003.
[48] L. Gray. A mathematican looks at Wolfram’s New Kind of Science. Notices of the AMS,50:200–211, 2003.
[49] L.O. Chua, S. Yoon, and R. Dogaru. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part I: Threshold of complexity. Int. J. Bifurcation Chaos, 12:2655–2766,2002.
[50] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part II: Universal neuron. Int. J. Bifurcation Chaos, 13:2377–2491, 2003.
[51] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part III: Predicting the unpredictable. Int. J. Bifurcation Chaos, 14:3689–3820, 2004.
[52] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science.Part IV: From bernoulli shift to 1/f spectrum. Int. J. Bifurcation Chaos,15:1045–1183, 2005.
[53] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part V: Fractals everywhere. Int. J. Bifurcation Chaos, 15:3701–3849, 2005.
[54] L.O. Chua, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wolfram’s newkind of science. Part VI: From time-reversible attractors to the arrow of time. Int. J. Bifurca-tion Chaos, 16:1097–1373, 2006.
[55] L.O. Chua, J. Guan, V.I. Sbitnev, and S. Yook. A nonlinear dynamics perspective of Wol-fram’s new kind of science. Part VII: Isles of Eden. Int. J. Bifurcation Chaos, 17:2839–3012,2007.
[56] L.O. Chua, K. Karacs, V.I. Sbitnev, J. Guan, and S. Yook. A nonlinear dynamics perspectiveof Wolfram’s new kind of science. Part VIII: More Isles of Eden. Int. J. Bifurcation Chaos,17:3741–3894, 2007.
[57] L.O. Chua. A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Science, Volume I.World Scientific, Singapore, 2006.
[58] L.O. Chua. A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Science, VolumeII. World Scientific, Singapore, 2007.
[59] P. Hogeweg. Cellular automata as a paradigm for ecological modeling. Applied Mathematicsand Computation, 27:81–100, 1988.
[60] P. Manneville, N. Boccara, G. Vichniac, and R. Bidaux. Cellular automata and the modelingof complex physical systems. Springer, Berlin, 1989.
[61] H. Baltzer, W.P. Braun, and W. Kohler. Celluar automata model for vegetable dynamics.Ecological Modelling, 107:113–125, 1998.
[62] R.M. Zorzenon, dos Santos and S. Coutinho. Dynamics of HIV infection: A cellular au-tomata approach. Phys. Rev. Lett., 87:168102, 2001.
[63] G. Qiu, D. Kandhai, and P.M.A. Sloot. Understanding the complex dynamics of stock mar-kets through cellular automata. Phys. Rev. E, 75:046116, 2007.
[64] S. Raghavan and S.S. Sahay. Modeling the grain growth kinetics by cellular automaton.Materials Science and Engineering, 445-446:203–209, 2007.
[65] W. Yuan and K.H. Tan. An evacuation model using cellular automata. Physica A, 384:549–566, 2007.
[66] K. Culik II and S Yu. Undecidability of ca classification schemes. Complex Systems, 2:177–190, 1988.
[67] K. Culik II, J Pachl, and S Yu. On the limit sets of cellular automata. SIAM J. Comput.,18(4):831, 1989.
[68] T.E. Ingerson and R.L. Buvel. Structure in asynchronous cellular automata. Physica D,10:59–68, 1984.
[69] F. Bagnoli, N. Boccara, and R. Rechtman. Nature of phase transitions in probabilistic cellularautomata with two absorbing states. Lect. Notes Comput. Sci., 2493:249–258, 2002.
[70] S.A. Billings and Y. Yang. Identification of probabilistic cellular automata. IEEE Transac-tions on Systems, Man and Cybernetics, 33:225–236, 2003.
[71] G. Grinstein, C. Jayaprakash, and Y. He. Statistical mechanics of probabilistic cellular au-tomata. Phys. Rev. Lett, 55:2527–2530, 1985.
[72] W. Just. Phase transitions in coupled map lattices and in associated probabilistic cellularautomata. Phys. Rev. E, 74:046209, 2006.
[73] K. Kaneko. Spatiotemporal intermittency in coupled map lattices. Prog. of Theo. Phy.,74:1033–1044, 1985.
[74] J.T. Dockery and A.E.R. Woodcock. The Military Landscape: Mathematical Models ofCombat. Cambridge, England: Woodhead Publishing Limited, 1993.
[75] S.A Kauffman. Emergent properties in random complex systems. Physica D, 10:146–156,1984.
[76] P. Halpern. Sticks and stones: a guide to structurally dynamic cellular automata. AmericanJournal of Physics, 57(5):405–408, May 1989.
[77] P. Halpern and G. Caltagirone. Behavior of topological cellular automata. Complex Syst.,4:623–651, 1990.
[78] G. Grossing and A. Zeilinger. Quantum cellular automata. Complex Syst., 2:197–208, 1988.
[79] M. Khatun, T. Barclay, I. Sturzu, and P.D. Tougaw. Fault tolerance properties in quantum-dotcellular automata devices. J. Phys. D: Appl. Phys., 39:1489–1494, 2006.
[80] A. Kay. Unifying quantum state transfer and state amplification. Phy. Rev. Lett., 98:010501,2007.
[81] B.F. Madore and W.L. Freedman. Computer simulations of the Belousov-Zhabotinsky reac-tion. Science, 222:615–616, 1983.
[82] R. Durrett and J. E. Steif. Some rigorous results for the Greenberg-Hastings model. Journalof Theoretical Probability, 4:669–690, 1991.
[83] J.M. Greenberg, B.D. Hassard, and S.P. Hastings. Pattern formation and periodic structuresin systems modelled by reaction-diffusion equations. Bulletin of the American MathematicalSociety, 84:1296–1327, 1978.
[84] J.M. Greenberg and S.P. Hastings. Spatial patterns for discrete models of diffusion in ex-citable media. SIAM Journal on Applied Mathematics, 34:515–523, 1978.
[85] J.M. Greenberg, C. Greene, and S. Hastings. A combinatorial problem arising in the study ofreaction-diffusion equations. SIAM Journal of Algebra and Discrete Mathematics, 1:34–42,1980.
[86] F. Blanchard, E. Formenti, and P. Ku?rka. Celluar automata in the cantor, besicovitch andweyl topological spaces. Complex Syst., 11:107–123, 1999.
[87] E. Formenti. On the sensitivity of additive cellular automata in besicovitch topologies. The-oret. Comput. Sci., 301:341–354, 2003.
[88] N. Romero, A. Rovella, and F. Vilamajo′. Remark on cellular automata and shift preservingmaps. Applied Mathematics Letters, 19:576–580, 2006.
[89] N. Chomsky. Three models for the description of language. IRE Trans. Info. Theo., IT2:113–129, 1956.
[90] P. Ku?rka. Languages, equicontinuity and attractors in cellular automata. Ergodic Theory &Dynamic system, 17:417–433, 1997.
[91] P. Ku?rka. Celluar automata with an infinite number of subshift attractors. Complex Systems,17:219–230, 2007.
[92] H. Umeo. Linear-time recognition of connectivity of binary images on 1-bit inter-cell com-munication cellular automaton. Parallel Computing, 27:587–599, 2001.
[93] J.L. Cardenas-Barrera, K.N. Plataniotis, and A.N. Venetsanopoulos. QCA implementation ofa multichannel filter for image processing. Mathematical Problems in Engineering, 8:87–99,2002.
[94] R.J. Chen and J.L. Lai. Image security system using recursive cellular automata substitution.Pattern Recognition, 40:1621–1631, 2007.
[95] K. Nagel and M. Shreckenberg. A cellular automaton model for freeway traffic. J. Phys. I.France, 2:2221–2229, 1992.
[96] M. Fukui and Y. Ishibashi. Traffic ?ow in 1D cellular automaton model including cars mov-ing with high speed. J. Phys. Soc. Japan, 65:1868–1870, 1996.
[97] E.G. Camparil and G. Levi. A cellular automata model for highway traffic. Eur. Phys. J. B,17:159–166, 2000.
[98] J. Wahle, L. Neubert, J. Esser, and M. Schreckenberg. A cellular automaton traffic ?owmodel for online simulation of traffic. Parallel Computing, 27:719–735, 2001.
[99] N. Moussa. Car accidents in cellular automata models for one-lane traffic ?ow. Phys. Rev.E, 68:036127, 2003.
[100] X.Q. Yang, W. Zhang, K. Qiu, W.T. Xu, G. Tang, and L. Ren. The relations of“go andstop”wave to car accidents in a cellular automaton with velocity-dependent randomization.Physica A, 384:589–599, 2007.
[101] D.G. Green. Cellular automata models in biology. Mathematical and Computer Modelling,13:69–74, 1990.
[102] G. Bard Ermentrout and Leah Edelstein-Keshet. Cellular automata approaches to biologicalmodeling. Journal of Theoretical Biology, 160:97–133, Jan 1993.
[103] C. Salzberg, A. Antony, and H. Sayama. Evolutionary dynamics of cellular automata-basedself-replicators in hostile environments. Biosystems, 78:119–134, 2004.
[104] R.D. Handy. Systems toxicology: using the systems biology approach to assess chemicalpollutants in the environment. Advances in Experimental Biology, 2:249–281, 2008.
[105] S. Wolfram. Cryptography with cellular automata. In Advances in Cryptology: Crypto’85Proceedings, Lecture Notes in Computer Science, 218 (Springer-Verlag) 429-432, 1986.
[106] D.R. Chowdhury, L.S. Gupta, and P.P. Chaudhuri. A class of two-dimensional cellular au-tomata and applications in random pattern testing. Journal of Electronic Testing: Theory andApplication, 5:65–80, 1994.
[107] M. Tomassini, M. Sipper, and M. Perrenoud. On the generation of high-quality randomnumbers by two-dimensional cellular automata. IEEE Transactions on Computers, 49:1146–1151, 2000.
[108] M. Tomassini and M. Perrenoud. Cryptography with cellular automata. Applied Soft Com-puting, 1:151–160, 2001.
[109] F. Seredynski, P. Bouvry, and A.Y. Zomaya. Celluar automata computations and secret keycryptography. Parallel Computing, 30:753–766, 2004.
[110] J. Sung, D. Hong, and S. Hong. Cryptanalysis of an involutional block cipher using cellularautomata. Information Processing Letters, 104:183–185, 2007.
[111] L.Z. Guo and S.A. Billings. Identification of binary cellular automata from spatio-temporalbinary patterns using a fourier representation. Int. J. Bifurcation Chaos, 17:1985–1996, 2007.
[112] A. Shreim, P. Grassberger, W. Nadler, B. Samuelsson, J. Socolar, and M. Paczuski. Networkanalysis of the state space of discrete dynamical systems. Phys. Rev. Lett., 98:198701, 2007.
[113] S. Adachi, J. Lee, F. Peper, and H. Umeo. Kaleidoscope of Life: A 24-neighbourhood outer-totalistic cellular automaton. Physica D, 237:800–817, 2008.
[114] J.Y. Ko, Y.C. Hung, M.C. Ho, and I.M. Jiang. Chaotic behavior in the disorder cellularautomata. Chaos, Solitons & Fractals, 36:934–939, 2008.
[115] J.R. Sa′nchez and R. Lo′pez-Ruiz. Symmetry pattern transition in cellular automata withcomplex behavior. Chaos, Solitons & Fractals, 37:638–642, 2008.
[116] A.R. Mikler, S. Venkatachalam, and K. Abbas. Modeling infiectious diseases using globalstochastic cellular automata. Journal of Biological Systems, 13:421–439, 2005.
[117] A.H. Encinas, L.H. Encinas, S.H. White, A.M. del Rey, and G.R. Sanchez. Simulation offorest fire fronts using cellular automata. Advances in Engineering Software, 38:372–378,2007.
[118] H. Yue, H. Hao, Y. Chen, and C. Shao. Simulation of pedestrian ?ow on square lattice basedon cellular automata model. Physica A, 384:567–588, 2007.
[119] I.G. Georgoudas, G.C. Sirakoulis, E.M. Scordilis, and I. Andreadis. A cellular automatonsimulation tool for modelling seismicity in the region of Xanthi. Environmental Modelling& Software, 22:1455–1464, 2007.
[120] M. Bartolozzi and A.W. Thomas. Stochastic cellular automata model for stock market dy-namics. Phys. Rev. E, 69:046112, 2004.
[121] P. Ku?rka. On the measure attractors of a cellular automaton. Discrete and Continuous Dy-namical Systems, Supplement Volume:524–535, 2005.
[122] E. Formenti and P. Ku?rka. Subshift attractors of cellular automata. Nonlinearity, 20:1–13,2007.
[123] A. Wuensche and M. Lesser. The Global Dynamics of Cellular Automata. Addision-Wesley,Reading, MA, 1992.
[124] L.O. Chua and L. Yang. Cellular neural networks: Theory. IEEE Trans. Circuits Syst.,35:1257–1272, 1988.
[125] L.O. Chua and L. Yang. Cellular neural networks: Applications. IEEE Trans. Circuits Syst.,35:1273–1290, 1988.
[126] J.M. Cruz and L.O. Chua. A cnn chip for connected component detection. IEEE Trans.Circuits Syst., 38:812–817, 1991.
[127] L.O. Chua, L. Yang, and K.R. Krieg. Signal processing using cellular neural networks.Journal of VLSI Signal Processing, 3:25–51, 1991.
[128] P. Szolgay, Vo¨ro¨s, and G. Ero¨ss. On the applications of the cellular neural network paradigmin mechanical vibrating systems. IEEE Trans. Circuits Syst. I: Fundamental Theory andApplications, 40:222–227, 1993.
[129] L.O. Chua, M. Hasler, G.S. Moschytz, and J. Neirynck. Autonomous cellular neural net-works: A unified paradigm for pattern formation and active wave propagation. IEEE Trans.Circuits Syst., 42:559–577, 1995.
[130] P. Arena, L. Fortuna, M. Frasca, and Patane′. A CNN-based chip for robot locomotion control.IEEE Trans. Circuits Syst.I: Regular Papers, 52:1862–1871, 2005.
[131] H. Aomori, T. Otake, N. Takahashi, and M. Tanaka. Sigma-delta cellular neural network for2D modulation. Neural Networks, 2008 Special Issue, 21:349–357, 2008.
[132] J.M. Cruz and L.O. Chua. A 16×16 cellular neural network universal chip: the first completesingle-chip dynamic computer array with distributed memory and with gray-scale input-output. Analog Integr. Circuits Sig. Process. J., 15:227–238, 1998.
[133] L.O. Chua and T. Roska. Celluar Neural Networks—Foundations and Primer. LectureNotes/EE129, University of California, Berkeley, 1997.
[134] L.O. Chua. CNN: A Paradigm for Complexity. World Scientific, Singapore, 1998.
[135] G. Qun, F. Philipp, R.M. Karl, and S.M. Geore. Fingerprint recognition using CNNs: Fin-gerprint preprocessing. In Proc. IEEE Int. Symp. Circuits and Systems(ISCAS2001), Sydney,Australia, volume 3, pages 433–436, 2001.
[136] Y. Lou, F. Chen, and J. Guan. Fingerprint feature extraction via CNN with von Neumannneighborhood. Int. J. Bifurcation Chaos, 17:4145–4151, 2007.
[137] F.Y. Chen, G.L. He, and G.R. Chen. Realization of Boolean functions via CNN with vonNeumann neighborhood. Int. J. Bifurcation Chaos, 16:1389–1403, 2006.
[138] M. Cook. Universality in elementary cellular automata. Complex Syst., 15:1–40, 2004.
[139] L.O. Chua and T. Roska. Celluar Neural Networks and Visual Computing: Foundations andApplications. Cambridge University Press, Cambridge, 2002.
[140] F.Y. Chen and G. Chen. Realization and bifurcation of boolean functions via cellular neuralnetworks. Int. J. Bifurcation Chaos, 15:2109–2129, 2005.
[141] P.M. Binder. Topological classification of cellular automata. J. Phys. A.: Math. Gen.,24:L31–L34, 1991.
[142] R. Badii and A. Politi. Thermodynamics and complexity of cellular automata. Phys. Rev.Lett., 78(3):444–447, 1997.
[143] D. Feldman and J. Crutchfield. Measures of statistical complexity: why. Phys. Lett. A,238:244–252, 1998.
[144] S. Sakai, M. Kanno, and Y. Saito. Quiescent string dominance parameter f and classificationof one-dimensional cellular automata. Phys. Rev. E, 69:066117, 2004.
[145] S. Wiggins. Introduction to Applied Nonlinear Dynamical Systems and Chaos(second edi-tion). Springer-Verlag, Berlin, NY, 2003.
[146] R. Alonso-Sanz. One-dimensional r=2 cellular automata with memory. Int. J. Bifurcationand Chaos, 14:3217–3248, 2004.
[147] J. Freire and J. Gallas. Synchronization and predictability under rule 52, a cellular automatonreputedly of class 4. Physics Letters A, 366:25–29, 2007.
[148] G. Cattnaneo, M. Finelli, and L. Margara. Investigating topological chaos by elementarycellular automata dynamics. Theoretical Computer Science, 244:219–241, 2000.
[149] M.S. Capcarrere, M. Sipper, and M. Tomassini. Two-state, r=1 cellular automaton that clas-sifies density. Phy. Rev. Lett., 77:4969–4971, 1996.
[150] D. A. Lind. Applications of ergodic theory and sofic systems to cellular automata. PhysicaD, 10:36–44, 1984.
[151] J.E. Hanson and J. Crutchfield. The attractor-basin portrait of a cellular automaton. Journalof Statistical Physics, 66:1415–1462, 1992.
[152] G. Cattnaneo, E. Formenti, G. Manzini, and L. Margara. Ergodicity, transitivity, and regular-ity for linear cellular automata over Zm. Theort. Comput. Sci., 233:147–164, 2000.
[153] H. Akin. On the ergodic properties of certain additive cellular automata over Zm. AppliedMathematics and Computation, 168:192–197, 2005.
[154] J. Milnor. On the entropy geometry of cellular automata. Complex Syst., 2:357–386, 1988.
[155] L.P. Hurd, J. Kari, and K. Culik. The topological entropy of cellular automata is uncom-putable. Ergodic Theory and Dynamical Systems, 12:255–265, 1992.
[156] M.A. Shereshevsky. Lyapunov exponents for one-dimensional cellular automata. J. Nonlin-ear Sci., 2:1–8, 1992.
[157] M. Finelli, G. Manzini, and L. Margara. Lyapunov exponents vs expansivity and sensitivityin cellular automata. J. Complexity, 14:210–233, 1998.
[158] P. Tisseur. Celluar automata and Lyapunov exponents. Nonlinearity, 13:1547–1560, 2000.
[159] M. Courbage and Kamin′ski. Space-time directional Lyapunov exponents for cellular au-tomata. Jour. Stat. Physics, 124:1499–1509, 2006.
[160] R. Dogaru and L.O. Chua. Cnn genes for one-dimensional cellular automata: A multi-nestedpiecewise-linear approach. Int. J. Bifurcation Chaos, 8:1987–2001, 1998.