A survey of cellular automata: types, dynamics, non-uniformity and applications. (English) Zbl 1530.68158
Summary: Cellular automata (CAs) are dynamical systems which exhibit complex global behavior from simple local interaction and computation. Since the inception of cellular automaton (CA) by von Neumann in 1950s, it has attracted the attention of several researchers over various backgrounds and fields for modeling different physical, natural as well as real-life phenomena. Classically, CAs are uniform. However, non-uniformity has also been introduced in update pattern, lattice structure, neighborhood dependency and local rule. In this survey, we tour to the various types of CAs introduced till date, the different characterization tools, the global behavior of CAs, like universality, reversibility, dynamics etc. Special attention is given to non-uniformity in CAs and especially to non-uniform elementary CAs, which have been very useful in solving several real-life problems.
References:
| [1] | Acerbi, L.; Dennunzio, A.; Formenti, E., Conservation of some dynamical properties for operations on cellular automata, Theor Comput Sci, 410, 38-40, 3685-3693 (2009) · Zbl 1171.68022 |
| [2] | Adak, S.; Naskar, N.; Maji, P.; Das, S., On synthesis of non-uniform cellular automata having only point attractors, J Cell Autom, 12, 1-2, 81-100 (2016) · Zbl 1432.37020 |
| [3] | Adamatzky, AI, Computation of shortest path in cellular automata, Math Comput Model, 23, 4, 105-113 (1996) · Zbl 0847.68072 |
| [4] | Adami, C., Self-organized criticality in living systems, Phys Lett A, 203, 1, 29-32 (1995) |
| [5] | Albert, J.; Culik, K. II, A simple universal cellular automaton and its one-way and totalistic version, Complex Syst, 1, 1-16 (1987) · Zbl 0655.68065 |
| [6] | Albicki A, Khare M (1987) Cellular automata used for test pattern generation. In: Proceedings of international conference of computer design, pp 56-59 |
| [7] | Alonso-Sanz, R.; Bull, L., Elementary cellular automata with minimal memory and random number generation, Complex Syst, 18, 2, 195-213 (2009) · Zbl 1177.68149 |
| [8] | Amoroso, S.; Cooper, G., The garden-of-eden theorem for finite configurations, Proc Am Math Soc, 26, 1, 158-164 (1970) · Zbl 0219.02025 |
| [9] | Amoroso, S.; Patt, YN, Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures, J Comput Syst Sci, 6, 448-464 (1972) · Zbl 0263.94019 |
| [10] | Arbib, MA, Simple self-reproducing universal automata, Inf Control, 9, 177-189 (1966) · Zbl 0143.02102 |
| [11] | Atrubin, AJ, A one-dimensional real-time iterative multiplier, IEEE Trans Electron Comput, EC-14, 3, 394-399 (1965) |
| [12] | Banda, P.; Caughman, J.; Pospichal, J., Configuration symmetry and performance upper bound of one-dimensional cellular automata for the leader election problem, J Cell Autom, 10, 1-2, 1-21 (2015) · Zbl 1338.68174 |
| [13] | Banks ER (1970) Universality in cellular automata. In: Proceedings of IEEE conference record of 11th annual symposium on switching and automata theory, 1970. IEEE, pp 194-215 |
| [14] | Banks ER (1971) Information processing and transmission in cellular automata. Ph.D. thesis, MIT |
| [15] | Bao, F., Cryptanalysis of a partially known cellular automata cryptosystem, IEEE Trans Comput, 53, 11, 1493-1497 (2004) |
| [16] | Bardell PH (1990) Analysis of cellular automata used as pseudo-random pattern generators. In: Proceedings of international test conference, pp 762-768 |
| [17] | Beckers, A.; Worsch, T., A perimeter-time ca for the queen bee problem, Parallel Comput, 27, 5, 555-569 (2001) · Zbl 0972.68116 |
| [18] | Benjamin, SC; Johnson, NF, A possible nanometer-scale computing device based on an adding cellular automaton, Appl Phys Lett, 70, 17, 2321-2323 (1997) |
| [19] | Betel, H.; de Oliveira, PPB; Flocchini, P., Solving the parity problem in one-dimensional cellular automata, Nat Comput, 12, 3, 323-337 (2013) · Zbl 1334.68140 |
| [20] | Bhattacharjee, K.; Das, S., Reversibility of \(d\)-state finite cellular automata, J Cell Autom, 11, 2-3, 213-245 (2016) · Zbl 1432.68272 |
| [21] | Bhattacharjee, K.; Paul, D.; Das, S., Pseudo-random number generation using a 3-state cellular automaton, Int J Mod Phys C, 28, 6, 1750-078 (2017) |
| [22] | Bhattacharjee S, Bhattacharya J, Chaudhuri PP (1995) An efficient data compression hardware based on cellular automata. In: Proceedings of data compression conference (DCC95), p 472 |
| [23] | Blanchard, F.; Maass, A., Dynamical properties of expansive one-sided cellular automata, Israel J Math, 99, 1, 149-174 (1997) · Zbl 0892.58042 |
| [24] | Blok, HJ; Bergersen, B., Synchronous versus asynchronous updating in the “game of life”, Phys Rev E, 59, 3876-3879 (1999) |
| [25] | Boccara, N.; Fukś, H., Cellular automaton rules conserving the number of active sites, J Phys A Math Gen, 31, 6007 (1998) · Zbl 0981.37002 |
| [26] | Boccara, N.; Fukś, H., Number-conserving cellular automaton rules, Fundam Inf, 52, 1-3, 1-13 (2002) · Zbl 1013.37006 |
| [27] | Boccara, N.; Roger, M., Some properties of local and nonlocal site exchange deterministic cellular automata, Int J Modern Phys C, 5, 3, 581-588 (1994) |
| [28] | Bohm, D., Wholeness and the implicate order, ISBN 0-203-99515-5 (1980), Abingdon: Routledge, Abingdon |
| [29] | Bouré, O.; Fatès, N.; Chevrier, V., Probing robustness of cellular automata through variations of asynchronous updating, Nat Comput, 11, 4, 553-564 (2012) · Zbl 1332.68154 |
| [30] | Burks, C.; Farmer, D., Towards modeling DNA sequences as automata, Phys D Nonlinear Phenom, 10, 1-2, 157-167 (1984) · Zbl 0556.92014 |
| [31] | Capobianco S (2007) Surjectivity and surjunctivity of cellular automata in besicovitch topology. In: Proceedings of international workshop on cellular automata and discrete complex systems, AUTOMATA 2007 |
| [32] | Cattaneo, G.; Formenti, E.; Margara, L.; Mauri, G., On the dynamical behavior of chaotic cellular automata, Theor Comput Sci, 217, 1, 31-51 (1999) · Zbl 0933.68096 |
| [33] | Cattaneo, G.; Finelli, M.; Margara, L., Investigating topological chaos by elementary cellular automata dynamics, Theor Comput Sci, 244, 1-2, 219-241 (2000) · Zbl 0945.68134 |
| [34] | Cattaneo, G.; Dennunzio, A.; Margara, L., Solution of some conjectures about topological properties of linear cellular automata, Theor Comput Sci, 325, 2, 249-271 (2004) · Zbl 1071.68066 |
| [35] | Cattaneo G, Dennunzio A, Formenti E, Provillard J (2009) Non-uniform cellular automata. In: Proceedings of 3rd international conference language and automata theory and applications, LATA, pp 302-313 · Zbl 1234.68277 |
| [36] | Cattell, K.; Muzio, JC, Synthesis of one-dimensional linear hybrid cellular automata, IEEE Trans Comput Aided Design Integr Circuits Syst, 15, 3, 325-335 (1996) |
| [37] | Cattell, K.; Zhang, S., Minimal cost one-dimensional linear hybrid cellular automata of degree through 500, J Electron Test Theory Appl, 6, 2, 255-258 (1995) |
| [38] | Ceccherini-Silberstein, TG; Machi, A.; Scarabotti, F., Amenable groups and cellular automata, Annales de l’institut Fourier, 49, 2, 673-685 (1999) · Zbl 0920.43001 |
| [39] | Chakraborty R, Chowdhury DR (2009) A novel seed selection algorithm for test time reduction in BIST. In: Proceedings of the 18th Asian test symposium, ATS 2009, Taiwan, pp 15-20 |
| [40] | Chakraborty, S.; Chowdhury, DR; Chaudhuri, PP, Theory and application of non-group cellular automata for synthesis of easily testable finite state machines, IEEE Trans Comput, 45, 7, 769-781 (1996) · Zbl 1055.68549 |
| [41] | Chattopadhyay, P.; Choudhury, PP; Dihidar, K., Characterisation of a particular hybrid transformation of two-dimensional cellular automata, Comput Math Appl, 38, 5-6, 207-216 (1999) · Zbl 0942.68074 |
| [42] | Chattopadhyay, S.; Adhikari, S.; Sengupta, S.; Pal, M., Highly regular, modular, and cascadable design of cellular automata-based pattern classifier, IEEE Trans VLSI Syst, 8, 6, 724-735 (2000) |
| [43] | Chaudhuri, PP; Chowdhury, DR; Nandi, S.; Chatterjee, S., Additive cellular automata-theory and applications, ISBN 0-8186-7717-1 (1997), Los Alamitos: IEEE Computer Society Press, Los Alamitos · Zbl 0944.68133 |
| [44] | Cheybani, S.; Kertész, J.; Schreckenberg, M., Stochastic boundary conditions in the deterministic nagel-schreckenberg traffic model, Phys Rev E, 63, 16, 107 (2000) · Zbl 0996.90020 |
| [45] | Chopard, B.; Droz, M., Cellular automata modeling of physical systems (1998), Cambridge: Cambridge University Press, Cambridge · Zbl 0973.82033 |
| [46] | Chowdhury DR (1994) Theory and applications of additive cellular automata for reliable and testable VLSI circuit design. Ph.D. thesis, IIT, Kharagpur |
| [47] | Chowdhury DR, Chakraborty S, Vamsi B, Chaudhuri PP (1993) Cellular automata based synthesis of easily and fully testable FSMs. In: Proceedings of international conference on computer aided design, ICCAD, pp 650-653 |
| [48] | Chowdhury, DR; Basu, S.; Gupta, IS; Chaudhuri, PP, Design of CAECC—cellular automata based error correcting code, IEEE Trans Comput, 43, 6, 759-764 (1994) · Zbl 1068.68673 |
| [49] | Cinkir, Z.; Akin, H.; Siap, I., Reversibilty of 1D cellular automata with periodic boundary over finite fields \({{\mathbb{Z}}}_p \), J Stat Phys, 143, 807-823 (2011) · Zbl 1219.68119 |
| [50] | Codd, EF, Cellular automata (1968), Cambridge: Academic Press Inc, Cambridge · Zbl 0213.18301 |
| [51] | Codenotti, B.; Margara, L., Transitive cellular automata are sensitive, Am Math Mon, 103, 1, 58-62 (1996) · Zbl 0853.68137 |
| [52] | Cole, SN, Real time computation by n-dimensional iterative arrays of finite state machines, IEEE Trans Comput, C-18, 55-77 (1969) |
| [53] | Comer JM, Cerda JC, Martinez CD, Hoe DH (2012) Random number generators using cellular automata implemented on FPGAs. In: Proceedings of 44th southeastern symposium on system theory (SSST), 2012, pp 67-72 |
| [54] | Cook, M., Universality in elementary cellular automata, Complex Syst, 15, 1, 1-40 (2004) · Zbl 1167.68387 |
| [55] | Cori, R.; Metivier, Y.; Zielonka, W., Asynchronous mappings and asynchronous cellular automata, Inf Comput, 106, 2, 159-202 (1993) · Zbl 0785.68068 |
| [56] | Culik, K., On invertible cellular automata, Complex Syst, 1, 6, 1035-1044 (1987) · Zbl 0657.68053 |
| [57] | Culik, K.; Dube, S., An efficient solution to the firing mob problem, Theor Comput Sci, 91, 57-69 (1991) · Zbl 0745.68025 |
| [58] | Culik, K.; Yu, S., Undecidability of cellular automata classification schemes, Complex Syst, 2, 177-190 (1988) · Zbl 0657.68054 |
| [59] | Culik, K.; Hard, LP; Yu, S., Computation theoretic aspects of cellular automata, Physica D, 45, 1-3, 357-378 (1990) · Zbl 0729.68052 |
| [60] | Darabos, C.; Giacobini, M.; Tomassini, M., Performance and robustness of cellular automata computation on irregular networks, Adv Complex Syst, 10, 85-110 (2007) · Zbl 1151.68033 |
| [61] | Das AK (1990) Additive cellular automata: theory and application as a built-in self-test structure. Ph.D. thesis, IIT, Kharagpur |
| [62] | Das, AK; Chaudhuri, PP, An efficient on-chip deterministic test pattern generation scheme, Microprocess Microprogr, 26, 195-204 (1989) |
| [63] | Das, AK; Chaudhuri, PP, Vector space theoretic analysis of additive cellular automata and its applications for pseudo-exhaustive test pattern generation, IEEE Trans Comput, 42, 3, 340-352 (1993) · Zbl 1395.68051 |
| [64] | Das, AK; Ganguly, A.; Dasgupta, A.; Bhawmik, S.; Chaudhuri, PP, Efficient characterisation of cellular automata, IEE Proc E Comput Digit Tech, 137, 1, 81-87 (1990) |
| [65] | Das AK, Saha D, Chowdhury AR, Misra S, Chaudhuri PP (1990b) Signature analyzer based on additive cellular automata. In: Proceedings of 20th fault tolerant computing systems, pp 265-272 |
| [66] | Das, AK; Sanyal, A.; Chaudhuri, PP, On characterization of cellular automata with matrix algebra, Inf Sci, 61, 3, 251-277 (1992) · Zbl 0800.68587 |
| [67] | Das S (2007) Theory and applications of nonlinear cellular automata in VLSI design. Ph.D. thesis, Bengal Engineering and Science University, Shibpur |
| [68] | Das S (2011) Characterization of non-uniform number conserving cellular automata. In: Proceedings of international workshop on cellular automata and discrete complex systems, AUTOMATA 2011, Chile, pp 17-28 |
| [69] | Das, S.; Chowdhury, DR, Cryptographically suitable maximum length cellular automata, J Cell Autom, 6, 6, 439-459 (2011) · Zbl 1236.68188 |
| [70] | Das, S.; Chowdhury, DR, CAR30: a new scalable stream cipher with rule 30, Cryptogr Commun, 5, 2, 137-162 (2013) · Zbl 1335.94045 |
| [71] | Das S, Sikdar BK (2008) Characterization of non-reachable states in irreversible ca state space. In: Proceedings of international conference on cellular automata, research and industry, ACRI 2008, Japan. Springer, Berlin, pp 160-167 · Zbl 1159.37306 |
| [72] | Das, S.; Sikdar, BK, Characterization of 1-D periodic boundary reversible ca, Electron Notes Theor Comput Sci, 252, 205-227 (2009) · Zbl 1338.68179 |
| [73] | Das, S.; Sikdar, BK, A scalable test structure for multicore chip, IEEE Trans CAD Integr Circuits Syst, 29, 1, 127-137 (2010) |
| [74] | Das S, Ganguly N, Sikdar BK, Chaudhuri PP (2003a) Design of a universal BIST (UBIST) structure. In: Proceedings of 16th international conference on VLSI design, pp 161-166 |
| [75] | Das S, Kundu A, Sen S, Sikdar BK, Chaudhuri PP (2003b) Non-linear celluar automata based PRPG design (without prohibited pattern set) in linear time complexity. In: Proceedings of Asian test symposium, pp 78-83 |
| [76] | Das, Sukanta; Sikdar, Biplab K.; Chaudhuri, P. Pal, Characterization of Reachable/Nonreachable Cellular Automata States, Lecture Notes in Computer Science, 813-822 (2004), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1116.68509 |
| [77] | Das, S.; Mukherjee, S.; Naskar, N.; Sikdar, BK, Characterization of single cycle ca and its application in pattern classification, Electron Notes Theor Comput Sci, 252, 181-203 (2009) · Zbl 1338.68178 |
| [78] | Das, Sukanta; Sarkar, Anindita; Sikdar, Biplab K., Synthesis of Reversible Asynchronous Cellular Automata for Pattern Generation with Specific Hamming Distance, Lecture Notes in Computer Science, 643-652 (2012), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg |
| [79] | Delorme, M.; Mazoyer, J.; Tougne, L., Discrete parabolas and circles on 2D cellular automata, Theor Comput Sci, 218, 2, 347-417 (1999) · Zbl 0916.68102 |
| [80] | Dennunzio, A.; Lena, PD; Formenti, E.; Margara, L., On the directional dynamics of additive cellular automata, Theor Comput Sci, 410, 47, 4823-4833 (2009) · Zbl 1180.68183 |
| [81] | Dennunzio, A.; Formenti, E.; Manzoni, L., Computing issues of asynchronous CA, Fundam Inf, 120, 2, 165-180 (2012) · Zbl 1283.68226 |
| [82] | Dennunzio, A.; Formenti, E.; Provillard, J., Non-uniform cellular automata: classes, dynamics, and decidability, Inf Comput, 215, 32-46 (2012) · Zbl 1260.68249 |
| [83] | Dennunzio, A.; Di Lena, P.; Formenti, E.; Margara, L., Periodic orbits and dynamical complexity in cellular automata, Fundam Informaticae, 126, 2-3, 183-199 (2013) · Zbl 1304.37013 |
| [84] | Dennunzio, A.; Formenti, E.; Manzoni, L.; Mauri, G., m-asynchronous cellular automata: from fairness to quasi-fairness, Nat Comput, 12, 4, 561-572 (2013) · Zbl 1333.68191 |
| [85] | Dennunzio, A.; Formenti, E.; Provillard, J., Local rule distributions, language complexity and non-uniform cellular automata, Theor Comput Sci, 504, 38-51 (2013) · Zbl 1297.68176 |
| [86] | Dennunzio, A.; Formenti, E.; Provillard, J., Three research directions in non-uniform cellular automata, Theor Comput Sci, 559, 73-90 (2014) · Zbl 1360.68611 |
| [87] | Dennunzio, A.; Formenti, E.; Weiss, M., Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues, Theor Comput Sci, 516, 40-59 (2014) · Zbl 1360.68612 |
| [88] | de Oliveira, GMB; Siqueira, SRC, Parameter characterization of two-dimensional cellular automata rule space, Physica D, 217, 1, 1-6 (2006) · Zbl 1110.68082 |
| [89] | de Oliveira PPB (2013) Conceptual connections around density determination in cellular automata. In: Proceedings of international workshop on cellular automata and discrete complex systems, AUTOMATA 2013, Germany, pp 1-14 · Zbl 1336.68174 |
| [90] | Devaney, RL, An introduction to chaotic dynamical systems (1986), Boston: Addison Wesley, Boston · Zbl 0632.58005 |
| [91] | Di Gregorio, S.; Trautteur, G., On reversibility in cellular automata, J Comput Syst Sci, 11, 3, 382-391 (1975) · Zbl 0327.94064 |
| [92] | Domosi, P.; Nehaniv, CL, Algebraic theory of automata networks: an introduction (2005), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 1070.68095 |
| [93] | Droste, M.; Gastin, P.; Kuske, D., Asynchronous cellular automata for pomsets, Theor Comput Sci, 247, 1-2, 1-38 (2000) · Zbl 0949.68086 |
| [94] | Dubacq, JC, How to simulate turing machines by invertible one-dimensional cellular automata, Int J Found Comput Sci, 6, 4, 395-402 (1995) · Zbl 0843.68076 |
| [95] | Durand, Bruno, Global properties of 2D cellular automata: some complexity results, Lecture Notes in Computer Science, 433-441 (1993), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 0925.68327 |
| [96] | Durand, B.; Formenti, E.; Róka, Z., Number-conserving cellular automata i: decidability, Theor Comput Sci, 299, 1-3, 523-535 (2003) · Zbl 1042.68076 |
| [97] | Durand, B.; Formenti, E.; Varouchas, G., On undecidability of equicontinuity classification for cellular automata, Discrete Math Theor Comput Sci, 3, 117-128 (2003) · Zbl 1073.68686 |
| [98] | Durand-Lose JO (1998) About the universality of the billiard ball model. In: Proceedings international colloquium universal machines and computations, MCU’98, France, pp 118-132 |
| [99] | Dyer, C., One-way bounded cellular automata, Inf Control, 44, 261-281 (1980) · Zbl 0442.68082 |
| [100] | Ermentrout, GB; Edelstein-Keshet, L., Cellular automata approaches to biological modeling, J Theor Biol, 160, 1, 97-133 (1993) |
| [101] | Fatès, N., Stochastic cellular automata solutions to the density classification problem—when randomness helps computing, Theory Comput Syst, 53, 2, 223-242 (2013) · Zbl 1286.68336 |
| [102] | Fatès, N., Guided tour of asynchronous cellular automata, J Cell Autom, 9, 5-6, 387-416 (2014) · Zbl 1338.68183 |
| [103] | Fatés N (2017) FiatLux: cellular automata and discrete complex systems simulator. http://fiatlux.loria.fr/. Accessed Aug 25, 2017 |
| [104] | Fatès, N.; Thierry, E.; Morvan, M.; Schabanel, N., Fully asynchronous behavior of double-quiescent elementary cellular automata, Theor Comput Sci, 362, 1-3, 1-16 (2006) · Zbl 1101.68058 |
| [105] | Finelli, M.; Manzini, G.; Margara, L., Lyapunov exponents versus expansivity and sensitivity in cellular automata, J Complex, 14, 2, 210-233 (1998) · Zbl 0920.68093 |
| [106] | Fischer, PC, Generation of primes by a one-dimensional real-time iterative array, J ACM, 12, 388-394 (1965) · Zbl 0173.19105 |
| [107] | Formenti, E.; Grange, A., Number conserving cellular automata ii: dynamics, Theor Comput Sci, 304, 269-290 (2003) · Zbl 1045.68094 |
| [108] | Formenti, E.; Imai, K.; Martin, B.; Yunès, JB; Calude, CS; Freivalds, R.; Kazuo, I., Advances on random sequence generation by uniform cellular automata, Computing with new resources: essays dedicated to jozef gruska on the occasion of his 80th birthday, 56-70 (2014), Cham: Springer, Cham · Zbl 1323.68392 |
| [109] | Fredkin, E.; Toffoli, T., Conservative logic, Int J Theor Phys, 21, 219-253 (1982) · Zbl 0496.94015 |
| [110] | Frisch, U.; Hasslacher, B.; Pomeau, Y., Lattice gas automata for the Navier-Stokes equation, Phys Rev Lett, 56, 14, 1505-1508 (1986) |
| [111] | Fukś, H., Solution of the density classification problem with two cellular automata rules, Phys Rev E, 55, R2081-R2084 (1997) |
| [112] | Fukś, H., Probabilistic cellular automata with conserved quantities, Nonlinearity, 17, 1, 159 (2004) · Zbl 1083.37010 |
| [113] | Gandin, CA; Rappaz, M., A 3D cellular automaton algorithm for the prediction of dendritic grain growth, Acta Mater, 45, 5, 2187-2195 (1997) |
| [114] | Ganguly N, Halder D, Deb J, Sikdar BK, Chaudhuri PP (2000) Hashing through cellular automata. In: Proceedings of 8th international conference of advance computing and communication, pp 95-101 |
| [115] | Ganguly, Niloy; Maji, Pradipta; Dhar, Sandip; Sikdar, Biplab K.; Chaudhuri, P. Pal, Evolving Cellular Automata as Pattern Classifier, Lecture Notes in Computer Science, 56-68 (2002), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1027.68628 |
| [116] | Ganguly, N.; Maji, P.; Sikdar, BK; Chaudhuri, PP, Generalized multiple attractor cellular automata (GMACA) For associative memory, Int J of Pattern Recognit Artif Intell, 16, 7, 781-795 (2002) |
| [117] | Ganguly N, Sikdar BK, Chaudhuri PP (2002c) Design of an on-chip test pattern generator without prohibitited pattern set (PPS). In: Proceedings of ASP-DAC/VLSI design 2002, India, pp 689-694 |
| [118] | Ganguly, N.; Sikdar, BK; Chaudhuri, PP, Exploring cycle structures of additive cellular automata, Fundam Inf, 87, 2, 137-154 (2008) · Zbl 1245.68142 |
| [119] | Gardner, M., On cellular automata self-reproduction, the garden of eden and the game of ‘Life’, Sci Am, 224, 2, 112-118 (1971) |
| [120] | Ghosh S, Laskar N, Mahapatra S, Chaudhuri PP (2007) Probabilistic cellular automata model for identification of cpg island in DNA string. In: Proceedings of Indian international conference on artificial intelligence (IICAI), pp 1490-1509 |
| [121] | Ghosh S, Bachhar T, Maiti NS, Mitra I, Chaudhuri PP (2010) Theory and application of equal length cycle cellular automata (ELCCA) for enzyme classification. In: Proceedings of international conference on cellular automata, research and industry, ACRI 2010, Italy, pp 46-57 · Zbl 1307.92076 |
| [122] | Ghosh, S.; Maiti, NS; Chaudhuri, PP; Sikdar, BK, On invertible three neighborhood null-boundary uniform cellular automata, Complex Syst, 20, 47-65 (2011) · Zbl 1251.68149 |
| [123] | Ghosh, Soumyabrata; Maiti, Nirmalya S.; Chaudhuri, Parimal Pal, Theory and Application of Restricted Five Neighborhood Cellular Automata (R5NCA) for Protein Structure Prediction, Lecture Notes in Computer Science, 360-369 (2012), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg |
| [124] | Ghosh S, Maiti NS, Chaudhuri PP (2014) Cellular automata model for protein structure synthesis (PSS). In: Proceedings of international conference on cellular automata, research and industry, ACRI 2014, Poland, pp 268-277 |
| [125] | Goles, E.; Moreira, A.; Rapaport, I., Communication complexity in number-conserving and monotone cellular automata, Theor Comput Sci, 412, 29, 3616-3628 (2011) · Zbl 1216.68172 |
| [126] | Golze, U., (a-)synchronous (non-)deterministic cell spaces simulating each other, J Comput Syst Sci, 17, 2, 176-193 (1978) · Zbl 0397.68049 |
| [127] | Golze, U.; Priese, L., Petri net implementations by a universal cell space, Inf Control, 53, 1-2, 121-138 (1982) · Zbl 0559.68056 |
| [128] | Grinstein, G.; Jayaprakash, C.; He, Y., Statistical mechanics of probabilistic cellular automata, Phys Rev Lett, 55, 2527-2530 (1985) |
| [129] | Guan, S.; Tan, SK, Pseudorandom number generation with self-programmable cellular automata, IEEE Trans CAD, 23, 7, 1095-1101 (2004) |
| [130] | Guan, S.; Zhang, S., An evolutionary approach to the design of controllable cellular automata structure for random number generation, IEEE Trans CAD, 7, 1, 23-36 (2003) |
| [131] | Hattori, T.; Takesue, S., Additive conserved quantities in discrete-time lattice dynamical systems, Physica D, 49, 3, 295-322 (1991) · Zbl 0755.58020 |
| [132] | Hazari, R.; Das, S., Number conservation property of elementary cellular automata under asynchronous update, Complex Syst, 23, 177-195 (2014) · Zbl 1357.68121 |
| [133] | Hedlund, GA, Endomorphisms and automorphisms of the shift dynamical system, Mathe Syst Theory, 3, 320-375 (1969) · Zbl 0182.56901 |
| [134] | Hemmerling, A., On the computational equivalence of synchronous and asynchronous cellular spaces, Elektronische Informationsverarbeitung und Kybernetik, 18, 7-8, 423-434 (1982) · Zbl 0511.68035 |
| [135] | Herman, GT; Liu, WH, The daughter of celia, the french flag, and the firing squad, SIMULATION, 21, 2, 33-41 (1973) |
| [136] | Hortensius, PD; McLeod, RD; Card, HC, Parallel random number generation for VLSI systems using cellular automata, IEEE Trans Comput, C-38, 10, 1466-1473 (1989) |
| [137] | Hortensius, PD; McLeod, RD; Pries, W.; Miller, DM; Card, HC, Cellular automata-based pseudorandom number generators for built-in self-test, IEEE Trans Comput Aided Design Integr Circuits Syst, 8, 8, 842-859 (1989) |
| [138] | Hortensius, PD; McLeod, RD; Card, HC, Cellular automata based signature analysis for built-in self-test, IEEE Trans Comput, C-39, 10, 1273-1283 (1990) |
| [139] | Imai, K.; Morita, K., A computation-universal two-dimensional 8-state triangular reversible cellular automaton, Theor Comput Sci, 231, 2, 181-191 (2000) · Zbl 0951.68086 |
| [140] | Ingerson, TE; Buvel, RL, Structure in asynchronous cellular automata, Physica D, 10, 1-2, 59-68 (1984) |
| [141] | Itô, M.; Ôsato, N.; Nasu, M., Linear cellular automata over \({{\mathbb{Z}}}_m\), J Comput Syst Sci, 27, 1, 125-140 (1983) · Zbl 0566.68047 |
| [142] | Jen, E., Invariant strings and pattern-recognizing properties of one-dimensional cellular automata, J Stat Phys, 43, 1, 243-265 (1986) |
| [143] | Jin, J.; Wu, ZH, A secret image sharing based on neighborhood configurations of 2-D cellular automata, Optics Laser Technol, 44, 3, 538-548 (2012) |
| [144] | Jump, JR; Kirtane, JS, On the interconnection structure of cellular automata networks, Inf Control, 24, 74-91 (1974) · Zbl 0274.94042 |
| [145] | Kari, J., Reversibility of 2D cellular automata is undecidable, Physica D, 45, 386-395 (1990) · Zbl 0729.68058 |
| [146] | Kari, J., The nilpotency problem of one-dimensional cellular automata, SIAM J Comput, 21, 3, 571-586 (1992) · Zbl 0761.68067 |
| [147] | Kari, J., Reversibility and surjectivity problems of cellular automata, J Comput Syst Sci, 48, 1, 149-182 (1994) · Zbl 0802.68090 |
| [148] | Kari, J., Reversible cellular automata, 57-68 (2005), Berlin: Springer, Berlin · Zbl 1132.68495 |
| [149] | Kari, J., Theory of cellular automata: a survey, Theor Comput Sci, 334, 1-3, 3-33 (2005) · Zbl 1080.68070 |
| [150] | Kari, J.; Le Gloannec, B., Modified traffic cellular automaton for the density classification task, Fundam Inf, 116, 1-4, 141-156 (2012) · Zbl 1241.68083 |
| [151] | Kayama, Yoshihiko, Network View of Binary Cellular Automata, Lecture Notes in Computer Science, 224-233 (2012), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg |
| [152] | Kayama, Y.; Imamura, Y., Network representation of the game of life, J Artif Intell Soft Comput Res, 1, 3, 233-240 (2011) |
| [153] | Kazar, O.; Slatnia, S., Evolutionary cellular automata for image segmentation and noise filtering using genetic algorithms, J Appl Comput Sci Math, 5, 10, 33-40 (2011) |
| [154] | Kerner, BS, Three-phase traffic theory and highway capacity, Physica A, 333, C, 379-440 (2004) |
| [155] | Khan AR (1998) Replacement of some graphics routines with the help of 2D cellular automata algorithms for faster graphics operations. Ph.D. thesis, University of Kashmir |
| [156] | Kohyama, T., Cellular automata with particle conservation, Progress Theoret Phys, 81, 1, 47-59 (1989) |
| [157] | Kohyama, T., Cluster growth in particle-conserving cellular automata, J Stat Phys, 63, 3-4, 637-651 (1991) |
| [158] | Kurka, P., Languages, equicontinuity and attractors in cellular automata, Ergod Theory Dyn Syst, 17, 2, 417-433 (1997) · Zbl 0876.68075 |
| [159] | Kurka, P., Cellular automata with vanishing particles, Fundam Inf, 58, 2003, 203-221 (2003) · Zbl 1111.68521 |
| [160] | Lafe, O., Data compression and encryption using cellular automata transforms, Eng Appl Artif Intell, 10, 6, 581-591 (1997) |
| [161] | Lafe OE (2002) Method and apparatus for video compression using sequential frame cellular automata transforms. US Patent 6,456,744 |
| [162] | Land, M.; Belew, RK, No perfect two-state cellular automata for density classification exists, Phys Rev Lett, 74, 5148-5150 (1995) |
| [163] | Langton, CG, Computation at the edge of chaos, Physica D, 42, 12-37 (1990) |
| [164] | Le Caër, G., Comparison between simultaneous and sequential updating in \(2^{n+1}-1\) cellular automata, Physica A, 157, 2, 669-687 (1989) · Zbl 0684.68071 |
| [165] | Legendi, T.; Katona, E., A 5 state solution of the early bird problem in a one dimensional cellular space, Acta Cybern, 5, 2, 173-179 (1981) · Zbl 0481.68053 |
| [166] | Legendi, T.; Katona, E., A solution of the early bird problem in an n-dimensional cellular space, Acta Cybern, 7, 1, 81-87 (1986) · Zbl 0608.68039 |
| [167] | Leporati, A.; Mariot, L., Cryptographic properties of bipermutive cellular automata rules, J Cell Autom, 9, 437-475 (2014) · Zbl 1338.94078 |
| [168] | Li J, Demaine E, Gymrek M (2010) Es.268 the mathematics in toys and games, spring 2010. (massachusetts institute of technology: Mit opencourseware). http://ocw.mit.edu. Accessed |
| [169] | Li, W.; Packard, NH; Langton, CG, Transition phenomena in cellular automata rule space, Physica D, 45, 77-94 (1990) · Zbl 0729.68060 |
| [170] | Lindgren, K.; Nordahl, MG, Universal computation in simple one-dimensional cellular automata, Complex Syst, 4, 3, 299-318 (1990) · Zbl 0724.68072 |
| [171] | Machì, A.; Mignosi, F., Garden of eden configurations for cellular automata on cayley graphs of groups, SIAM J Discrete Math, 6, 1, 44-56 (1993) · Zbl 0768.68103 |
| [172] | Maiti NS, Munshi S, Chaudhuri PP (2006) An analytical formulation for cellular automata (CA) based solution of density classification task (DCT). In: Proceedings of international conference on cellular automata, research and industry, ACRI 2006. Springer, pp 147-156 · Zbl 1155.68462 |
| [173] | Maiti, NS; Ghosh, S.; Munshi, S.; Chaudhuri, PP, Linear time algorithm for identifying the invertibility of null-boundary three neighborhood cellular automata, Complex Syst, 19, 1, 89-113 (2010) · Zbl 1217.68144 |
| [174] | Maji P (2005) Cellular automata evolution for pattern recognition. Ph.D. thesis, Jadavpur University, Kolkata |
| [175] | Maji, Pradipta; Chaudhuri, P. Pal, FMACA: A Fuzzy Cellular Automata Based Pattern Classifier, Database Systems for Advanced Applications, 494-505 (2004), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg |
| [176] | Maji, P.; Chaudhuri, PP, Fuzzy cellular automata for modeling pattern classifier, IEICE Trans Inf Syst, E88-D, 4, 691-702 (2005) |
| [177] | Maji, P.; Ganguly, N.; Chaudhuri, PP, Error correcting capability of cellular automata based associative memory, IEEE Trans Syst Man Cybern A, 33, 4, 466-480 (2003) |
| [178] | Maji, P.; Shaw, C.; Ganguly, N.; Sikdar, BK; Chaudhuri, PP, Theory and application of cellular automata for pattern classification, Fundam Inf Cell Autom, 58, 3, 321-354 (2003) · Zbl 1108.68535 |
| [179] | Manning, FB, An approach to highly integrated, computer-maintained cellular arrays, IEEE Trans Comput, C-26, 536-552 (1977) |
| [180] | Manzoni, L., Asynchronous cellular automata and dynamical properties, Nat Comput, 11, 2, 269-276 (2012) · Zbl 1339.37018 |
| [181] | Manzoni, L.; Umeo, H., The firing squad synchronization problem on ca with multiple updating cycles, Theor Comput Sci, 559, 108-117 (2014) · Zbl 1360.68616 |
| [182] | Margenstern, M., About the garden of eden theorems for cellular automata in the hyperbolic plane, Electron Notes Theor Comput Sci, 252, 93-102 (2009) · Zbl 1338.68185 |
| [183] | Margenstern, M.; Morita, K., A polynomial solution for 3-sat in the space of cellular automata in the hyperbolic plane, J Univ Comput Sci, 5, 9, 563-573 (1999) · Zbl 0968.68105 |
| [184] | Margenstern, M.; Morita, K., Np problems are tractable in the space of cellular automata in the hyperbolic plane, Theor Comput Sci, 259, 1-2, 99-128 (2001) · Zbl 0972.68119 |
| [185] | Margolus, N., Physics-like models of computation, Physica D, 10, 1-2, 81-95 (1984) · Zbl 0563.68051 |
| [186] | Mariot, Luca, Asynchrony Immune Cellular Automata, Lecture Notes in Computer Science, 176-181 (2016), Cham: Springer International Publishing, Cham · Zbl 1392.68275 |
| [187] | Mariot, L.; Leporati, A.; Dennunzio, A.; Formenti, E., Computing the periods of preimages in surjective cellular automata, Nat Comput, 16, 3, 367-381 (2017) · Zbl 1530.68178 |
| [188] | Marr, C.; Hütt, MT, Outer-totalistic cellular automata on graphs, Phys Lett A, 373, 5, 546-549 (2009) · Zbl 1227.37006 |
| [189] | Martin, B., A universal cellular automata in quasi-linear time and its s-m-n form, Theor Comput Sci, 123, 2, 199-237 (1994) · Zbl 0801.68116 |
| [190] | Martin, O.; Odlyzko, AM; Wolfram, S., Algebraic properties of cellular automata, Commun Math Phys, 93, 219-258 (1984) · Zbl 0564.68038 |
| [191] | Martinez, GJ; McIntosh, HV; Mora, JCST; Vergara, SVC, Determining a regular language by glider-based structures called phases \(f_i\_1\) in rule 110, J Cell Autom, 3, 3, 231-270 (2008) · Zbl 1161.68606 |
| [192] | Maruoka, A.; Kimura, M., Condition for injectivity of global maps for tessellation automata, Inf Control, 32, 2, 158-162 (1976) · Zbl 0338.94030 |
| [193] | Maruoka, A.; Kimura, M., Injectivity and surjectivity of parallel maps for cellular automata, J Comput Syst Sci, 18, 1, 47-64 (1979) · Zbl 0411.68047 |
| [194] | Matsukidaira, J.; Nishinari, K., Euler-Lagrange correspondence of cellular automaton for traffic-flow models, Phys Rev Lett, 90, 088,701(1-4) (2003) |
| [195] | Mazoyer J, Nichitiu C, Rémila E (1999) Compass permits leader election. In: Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms, society for industrial and applied mathematics, SODA’99, pp 947-948 · Zbl 0934.68014 |
| [196] | McCulloch, WS; Pitts, W., A logical calculus of the ideas immanent in nervous activity, Bull Math Biophys, 5, 4, 115-133 (1943) · Zbl 0063.03860 |
| [197] | Miller DB, Fredkin E (2005) Two-state, reversible, universal cellular automata in three dimensions. In: Proceedings of the 2nd conference on computing frontiers. ACM, pp 45-51 |
| [198] | Misra S, Mitra B, Chaudhuri PP (1992) Synthesis of self-testable sequential logic using programmable cellular automata. In: Proceedings of international conference on VLSI design, pp 193-198 |
| [199] | Mitchell, M.; Hraber, PT; Crutchfield, JP, Revisiting the edge of chaos: evolving cellular automata to perform computations, Complex Syst, 7, 89-130 (1993) · Zbl 0834.68086 |
| [200] | Mitra B, Panda PR, Chaudhuri PP (1991) A flexible scheme for state assignment based on characteristics of the FSM. In: Proceedings of international conference on computer aided design, ICCAD, California, pp 226-229 |
| [201] | Mitra S, Das S, Chaudhuri PP, Nandi S (1996) Architecture of a VLSI chip for modeling amino acid sequence in proteins. In: Proceedings of 9th international conference on VLSI design, 1996, pp 316-317 |
| [202] | Mo, Y.; Ren, B.; Yang, W.; Shuai, J., The 3-dimensional cellular automata for hiv infection, Physica A, 399, 31-39 (2014) · Zbl 1395.92158 |
| [203] | Moore, EF, Machine models of self-reproduction, Proc Symp Appl Math, 14, 17-33 (1962) · Zbl 0126.32408 |
| [204] | Mora, JCST; Martínez, GJ; McIntosh, HV, The inverse behavior of a reversible one-dimensional cellular automaton obtained by a single welch diagram, J Cell Autom, 1, 1, 25-39 (2006) · Zbl 1135.68494 |
| [205] | Mora, JCST; Hernandez, MG; Vergara, SVC, Pair diagram and cyclic properties characterizing the inverse of reversible automata, J Cell Autom, 3, 3, 205-218 (2008) · Zbl 1161.68607 |
| [206] | Moraal, H., Graph-theoretical characterization of invertible cellular automata, Physica D, 141, 1, 1-18 (2000) · Zbl 0970.68111 |
| [207] | Morales, FJ; Crutchfield, JP; Mitchell, M., Evolving two-dimensional cellular automata to perform density classification: a report on work in progress, Parallel Comput, 27, 571-585 (2001) · Zbl 0972.68117 |
| [208] | Moreira, A., Universality and decidability of number-conserving cellular automata, Theor Comput Sci, 292, 3, 711-721 (2003) · Zbl 1026.68094 |
| [209] | Moreira, J.; Deutsch, A., Cellular automaton models of tumor development: a critical review, Adv Complex Syst, 05, 2-3, 247-267 (2002) · Zbl 1020.92016 |
| [210] | Moreno, JL; Whitin, ES; Jennings, HH, Application of the group method to classification (1932), New York: National Committee on Prisons and Prison Labor, New York |
| [211] | Morita, K., Reversible simulation of one-dimensional irreversible cellular automata, Theor Comput Sci, 148, 1, 157-163 (1995) · Zbl 0873.68141 |
| [212] | Morita, K., Reversible computing and cellular automata-a survey, Theor Comput Sci, 395, 1, 101-131 (2008) · Zbl 1145.68036 |
| [213] | Morita K (2016) Universality of 8-state reversible and conservative triangular partitioned cellular automata. In: International conference on cellular automata. Springer, pp 45-54 · Zbl 1392.68277 |
| [214] | Morita, K.; Harao, M., Computation universality of one dimensional reversible injective cellular automata, IEICE Trans E, 72, 758-762 (1989) |
| [215] | Morita K, Imai K (1998) Number-conserving reversible cellular automata and their computation-universality. In: Proceedings of satellite workshop on cellular automata MFCS’98, pp 51-68 · Zbl 1014.68102 |
| [216] | Morita, K.; Margenstern, M.; Imai, K., Universality of reversible hexagonal cellular automata, RAIRO Theor Inf Appl, 33, 6, 535-550 (1999) · Zbl 0953.68099 |
| [217] | Morita K, Tojima Y, Imai K (1999) A simple computer embedded in a reversible and number conserving two-dimensional cellular space. In: Proceedings of LA Symposium’99, Hakone · Zbl 1007.68126 |
| [218] | Myhill, J., The converse of moore’s garden of eden theorem, Proc Am Math Soc, 14, 685-686 (1963) · Zbl 0126.32501 |
| [219] | Nagel, K., Particle hopping models and traffic flow theory, Phys Rev E, 53, 4655-4672 (1996) |
| [220] | Nagel, K.; Schreckenberg, M., A cellular automaton model for freeway traffic, J Phys I, 2, 12, 2221-2229 (1992) |
| [221] | Nakamura, K., Asynchronous cellular automata and their computational ability, Syst Comput Controls, 5, 5, 58-66 (1974) |
| [222] | Nakamura, K., Synchronous to asynchronous transformation of polyautomata, J Comput Syst Sci, 23, 1, 22-37 (1981) · Zbl 0465.68027 |
| [223] | Nandi, S.; Chaudhuri, PP, Analysis of periodic and intermediate boundary 90/150 cellular automata, IEEE Trans Comput, 45, 1, 1-12 (1996) · Zbl 1046.68074 |
| [224] | Nandi, S.; Kar, BK; Chaudhuri, PP, Theory and application of cellular automata in cryptography, IEEE Trans Comput, 43, 12, 346-357 (1994) |
| [225] | Naskar N (2015) Characterization and synthesis of non-uniform cellular automata with point state attractors. Ph.D. thesis, Indian Institute of Engineering Science and Technology, Shibpur |
| [226] | Neumann, JV, Theory of self-reproducing automata (1966), Champaign: University of Illinois Press, Champaign |
| [227] | Newman, MEJ; Watts, DJ, Scaling and percolation in the small-world network model, Phys Rev E, 60, 6, 7332-7342 (1999) |
| [228] | Nishio H (1981) Real time sorting of binary numbers by one-dimensional cellular automata. Technical report, Kyoto University |
| [229] | Nishio, H.; Kobuchi, Y., Fault tolerant cellular space, J Comput Syst Sci, 11, 150-170 (1975) · Zbl 0319.94029 |
| [230] | Noguchi, K., Simple 8-state minimal time solution to the firing squad synchronization problem, Theor Comput Sci, 314, 3, 303-334 (2004) · Zbl 1072.68071 |
| [231] | Ollinger, Nicolas, The Quest for Small Universal Cellular Automata, Automata, Languages and Programming, 318-329 (2002), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1056.68104 |
| [232] | Ollinger N (2003) The intrinsic universality problem of one-dimensional cellular automata. In: Proceedings of international symposium on theoretical aspects of computer science, STACS 2003. Springer, pp 632-641 · Zbl 1035.68066 |
| [233] | Ollinger, N.; Richard, G., Four states are enough, Theor Comput Sci, 412, 22-32 (2011) · Zbl 1207.68217 |
| [234] | Packard, NH; Wolfram, S., Two-dimensional cellular automata, J Stat Phys, 38, 5-6, 901-946 (1985) · Zbl 0625.68038 |
| [235] | Paul K, Chowdhury DR (2000) Application of GF \((2^p)\) CA in burst error correcting codes. In: Proceedings of international conference of VLSI design, pp 562-567 |
| [236] | Paul, Kolin; Choudhury, D. Roy; Chaudhuri, P. Pal, Cellular Automata Based Transform Coding for Image Compression, Lecture Notes in Computer Science, 269-273 (1999), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg |
| [237] | Paul K, Chowdhury DR, Chaudhuri PP (2000) Scalable pipelined micro-architecture for wavelet transform. In: Proceedings of international conference on VLSI design, pp 144-147 |
| [238] | Pighizzini, G., Asynchronous automata versus asynchronous cellular automata, Theor Comput Sci, 132, 1-2, 179-207 (1994) · Zbl 0826.68081 |
| [239] | Pivato, M., Conservation laws in cellular automata, Nonlinearity, 15, 6, 1781 (2002) · Zbl 1013.37008 |
| [240] | Pries, W.; Thanailakis, A.; Card, HC, Group properties of cellular automata and VLSI applications, IEEE Trans Comput, C-35, 12, 1013-1024 (1986) · Zbl 0615.68043 |
| [241] | Provillard J, Formenti E, Dennunzio A (2011) Non-uniform cellular automata and distributions of rules. arXiv preprint arXiv:11081419 · Zbl 1297.68176 |
| [242] | Raghavan, R., Cellular automata in pattern recognition, Inf Sci, 70, 145-177 (1993) |
| [243] | Martın del Rey, A.; Rodrıguez Sınchez, G., Reversibility of linear cellular automata, Appl Math Comput, 217, 21, 8360-8366 (2011) · Zbl 1219.68120 |
| [244] | Richardson, D., Tessellations with local transformations, J Comput Syst Sci, 6, 373-388 (1972) · Zbl 0246.94037 |
| [245] | Roncken M, Stevens K, Pendurkar R, Rotem S, Chaudhuri PP (2000) Ca-bist for asynchronous circuits: a case study on the rappid asynchronous instruction length decoder. In: Proceedings of advanced research in asynchronous circuits and systems (ASYNC 2000), pp 62-72 |
| [246] | Rosenstiehl, P.; Fiksel, JR; Holliger, A.; Read, RC, Intelligent graphs: networks of finite automata capable of solving graph problems, Graph theory and computing, 219-265 (1972), New York: Academic press, New York · Zbl 0265.94030 |
| [247] | Rosin, PL, Training cellular automata for image processing, Trans Imge Process, 15, 7, 2076-2087 (2006) |
| [248] | Rosin, PL, Image processing using 3-state cellular automata, Comput Vis Image Underst, 114, 7, 790-802 (2010) |
| [249] | Roy, S.; Das, S., Distributed mutual exclusion problem in cellular automata, J Cell Autom, 12, 6, 493-512 (2017) · Zbl 1432.68292 |
| [250] | Ruxton, G.; Saravia, LA, The need for biological realism in the updating of cellular automata models, Ecol Model, 107, 2-3, 105-112 (1998) |
| [251] | Sadeghi, S.; Rezvanian, A.; Kamrani, E., An efficient method for impulse noise reduction from images using fuzzy cellular automata, AEU Int J Electron Commun, 66, 9, 772-779 (2012) |
| [252] | Salo, V., Realization problems for nonuniform cellular automata, Theor Comput Sci, 559, 91-107 (2014) · Zbl 1360.68619 |
| [253] | Santos J, Villot P, Diéguez M (2013) Protein folding with cellular automata in the 3d hp model. In: Proceedings of the 15th annual conference companion on genetic and evolutionary computation, GECCO’13, pp 1595-1602 |
| [254] | dos Santos, RMZ; Coutinho, S., Dynamics of HIV approach: a cellular automata approach, Phys Rev Lett, 87, 168102 (2001) |
| [255] | Saraniti, M.; Goodnick, SM, Hybrid fullband cellular automaton/monte carlo approach for fast simulation of charge transport in semiconductors, IEEE Trans Electron Devices, 47, 10, 1909-1916 (2000) |
| [256] | Sarkar, A.; Mukherjee, A.; Das, S., Reversibility in asynchronous cellular automata, Complex Syst, 21, 1, 71 (2012) · Zbl 1485.68155 |
| [257] | Sarkar, P., A brief history of cellular automata, ACM Comput Surv, 32, 1, 80-107 (2000) |
| [258] | Sarkar, P.; Barua, R., Multi-dimensional \(\sigma \)-automata, \( \pi \)-polynomial and generalized \(s\)-matrices, Theor Comput Sci, 197, 1-2, 111-138 (1998) · Zbl 0902.68125 |
| [259] | Sato, T.; Honda, N., Certain relations between properties of maps of tessellation automata, J Comput Syst Sci, 15, 2, 121-145 (1977) · Zbl 0379.94068 |
| [260] | Seredynski, F.; Bouvry, P.; Zomaya, AY, Cellular automata computations and secret key cryptography, Parallel Comput, 30, 5-6, 753-766 (2004) |
| [261] | Seredynski, M.; Bouvry, P., Block cipher based on reversible cellular automata, New Gener Comput, 23, 3, 245-258 (2005) · Zbl 1103.68049 |
| [262] | Serra, M.; Slater, T.; Muzio, JC; Miller, DM, The analysis of one-dimensional linear cellular automata and their aliasing properties, IEEE Trans CAD, 9, 7, 767-778 (1990) |
| [263] | Sethi B, Das S (2015) Convergence of asynchronous cellular automata (under null boundary condition) and their application in pattern classification. In: Recent advances in natural computing: selected results from the IWNC 7 symposium, Springer Japan, pp 35-55 |
| [264] | Sethi, B.; Das, S.; Mueller, P.; Thampi, SM; Alam Bhuiyan, MZ; Ko, R.; Doss, R.; Alcaraz Calero, JM, On the use of asynchronous cellular automata in symmetric-key cryptography, Security in computing and communications: 4th international symposium, SSCC 2016, Jaipur, India, Sept 21-24, 2016, Proceedings, 30-41 (2016), Singapore: Springer, Singapore |
| [265] | Sethi B, Fatès N, Das S (2014) Reversibility of elementary cellular automata under fully asynchronous update. In: Proceedings of 11th annual conference theory and applications of models of computation, TAMC 2014, India. Springer, pp 39-49 · Zbl 1405.68207 |
| [266] | Sethi, B.; Roy, S.; Das, S., Asynchronous cellular automata and pattern classification, Complexity, 21, S1, 370-386 (2016) |
| [267] | Shaw C, Chatterji D, Maji P, Sen S, Roy BN, Chaudhuri PP (2003) A pipeline architecture for encompression (encryption + compression) technology. In: Proceedings of VLSI design, pp 277-282 |
| [268] | Shaw C, Maji P, Saha S, Sikdar BK, Roy S, Chaudhuri PP (2004a) Cellular automata based encompression technology for voice data. In: Proceedings of international conference on cellular automata, research and industry, ACRI 2004, Netherlands, pp 258-267 · Zbl 1116.68528 |
| [269] | Shaw C, Sikdar BK, Maiti NC (2004b) CA based document compression technology. In: Proceedings of 11th international conference on neural information processing, ICONIP, pp 679-685 |
| [270] | Shaw C, Das S, Sikdar BK (2006) Cellular automata based encoding technique for wavelet transformed data targeting still image compression. In: Proceedings of international conference on cellular automata, research and industry, ACRI 2006, France, pp 141-146 · Zbl 1155.68556 |
| [271] | Shereshevsky, MA, Lyapunov exponent for one-dimensional cellular automata, J Nonlinear Sci, 2, 1-8 (1992) · Zbl 0872.58038 |
| [272] | Siap, I.; Akin, H.; Uğuz, S., Structure and reversibility of 2d hexagonal cellular automata, Comput Math Appl, 62, 11, 4161-4169 (2011) · Zbl 1236.68191 |
| [273] | Sikdar BK, Paul K, Biswas GP, Boppana V, Yang C, Mukherjee S, Chaudhuri PP (2000) Theory and application of gf \((2^p)\) cellular automata as on-chip test pattern generator. In: Proceedings of 13th international conference on VLSI design, 2000, pp 556-561 |
| [274] | Sikdar BK, Ganguly N, Karmakar A, Chowdhury S, Chaudhuri PP (2001) Multiple attractor cellular automata for hierarchical diagnosis of VLSI circuits. In: Proceedings of 10th Asian test symposium, Japan, pp 385-390 |
| [275] | Sikdar, BK; Ganguly, N.; Chaudhuri, PP, Design of hierarchical cellular automata for on-chip test pattern generator, IEEE Trans Comput Aided Design Integr Circuits Syst, 21, 12, 1530-1539 (2002) |
| [276] | Sipper, M.; Tomassini, M., Generating parallel random number generators by cellular programming, Int J Modern Phys, 7, 2, 180-190 (1996) |
| [277] | Smith, AR III, Cellular automata complexity trade-offs, Inf Control, 18, 466-482 (1971) · Zbl 0222.94057 |
| [278] | Smith, AR III, Simple computation-universal cellular spaces, J ACM, 18, 3, 339-353 (1971) · Zbl 0221.94071 |
| [279] | Smith AR III (1976) Introduction to and survey of polyautomata theory. In: Automata languages development, pp 405-422 |
| [280] | Soto, JMG, Computation of explicit preimages in one-dimensional cellular automata applying the de bruijn diagram, J Cell Autom, 3, 3, 219-230 (2008) · Zbl 1158.68025 |
| [281] | Stratmann, M.; Worsch, T., Leader election in d-dimensional ca in time diam log(diam), Future Gener Comput Syst, 18, 7, 939-950 (2002) · Zbl 1042.68082 |
| [282] | Sutner, K., De bruijin graphs and linear cellular automata, Complex Syst, 5, 1, 19-30 (1991) · Zbl 0764.68100 |
| [283] | Suzudo, T., Spatial pattern formation in asynchronous cellular automata with mass conservation, Physica A, 343, 185-200 (2004) |
| [284] | Takesue, S., Staggered invariants in cellular automata, Complex Syst, 9, 2, 149-168 (1995) · Zbl 0843.68078 |
| [285] | Terrier, V., Two-dimensional cellular automata and their neighborhoods, Theor Comput Sci, 312, 2, 203-222 (2004) · Zbl 1070.68099 |
| [286] | Thatcher JW (1964) Universality in the von neumann cellular model. Technical report, DTIC Document · Zbl 0235.02035 |
| [287] | Toffoli, T., Computation and construction universality of reversible cellular automata, J Comput Syst Sci, 15, 213-231 (1977) · Zbl 0364.94085 |
| [288] | Toffoli, T.; Margolus, N., Cellular automata machines: a new environment for modeling (1987), Cambridge: MIT Press, Cambridge |
| [289] | Toffoli, T.; Margolus, NH, Invertible cellular automata: a review, Physica D, 45, 1, 229-253 (1990) · Zbl 0729.68066 |
| [290] | Tomassini, Marco, Generalized Automata Networks, Lecture Notes in Computer Science, 14-28 (2006), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1155.68467 |
| [291] | Tomassini, Marco; Venzi, Mattias, Artificially Evolved Asynchronous Cellular Automata for the Density Task, Lecture Notes in Computer Science, 44-55 (2002), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1027.68640 |
| [292] | Tomassini, M.; Sipper, M.; Perrenoud, M., On the generation of high-quality random numbers by two-dimensional cellular automata, IEEE Trans Comput, 49, 10, 1146-1151 (2000) · Zbl 1315.68187 |
| [293] | Tomassini, M.; Giacobini, M.; Darabos, C., Evolution and dynamics of small-world cellular automata, Complex Syst, 15, 261-284 (2005) · Zbl 1167.68395 |
| [294] | Tsalides, P., Cellular automata based built-in self-test structures for VLSI systems, Electron Lett, 26, 17, 1350-1352 (1990) |
| [295] | Tsalides, P.; York, TA; Thanailakis, A., Pseudo-random number generators for VLSI systems based on linear cellular automata, IEEE Proc E Comput Digit Tech, 138, 4, 241-249 (1991) |
| [296] | Uğuz, S.; Akin, H.; Siap, I., Reversibility algorithms for 3-state hexagonal cellular automata with periodic boundaries, Int J Bifurc Chaos, 23, 6, 1350101 (2013) · Zbl 1272.37010 |
| [297] | Uğuz, S.; Sahin, U.; Akin, H.; Siap, I., Self-replicating patterns in 2D linear cellular automata, Int J Bifurc Chaos, 24, 1, 1430,002 (2014) · Zbl 1284.37010 |
| [298] | Umeo, H.; Hisaoka, M.; Sogabe, T., A survey on optimum-time firing squad synchronization algorithms for one-dimensional cellular automata, Intl J Unconv Comput, 1, 4, 403-426 (2005) |
| [299] | Vichniac, GY, Simulating physics with cellular automata, Physica D, 10, 1, 96-116 (1984) · Zbl 0563.68053 |
| [300] | Vollmar, R., On two modified problems of synchronization in cellular automata, Acta Cybern, 3, 4, 293-300 (1977) · Zbl 0393.68055 |
| [301] | Voorhees, B., Some parameters characterizing cellular automata rules, Complex Syst, 11, 5, 373-386 (1997) · Zbl 0954.68106 |
| [302] | Voorhees, B., Remarks on applications of de bruijn diagrams and their fragments, J Cell Autom, 3, 3, 187-204 (2008) · Zbl 1161.68610 |
| [303] | Wang Q, Yu S, Ding W, Leng M (2008) Generating high-quality random numbers by cellular automata with pso. In: Proceedings of 4th international conference on natural computation, ICNC’08, pp 430-433 |
| [304] | Ward, T., Automorphisms of \({{\mathbb{Z}}}^d\)-subshifts of finite type, Indag Math, 5, 4, 495-504 (1994) · Zbl 0823.28007 |
| [305] | Watts, DJ; Strogatz, SH, Collective dynamics of ‘small-world’ networks, Nature, 393, 6684, 440-442 (1998) · Zbl 1368.05139 |
| [306] | Wolfram, S., Statistical mechanics of cellular automata, Rev Mod Phys, 55, 3, 601-644 (1983) · Zbl 1174.82319 |
| [307] | Wolfram, S., Universality and complexity in cellular automata, Physica, 10, 1-35 (1984) · Zbl 0562.68040 |
| [308] | Wolfram, S., Origins of randomness in physical systems, Phys Rev Lett, 55, 449-452 (1985) |
| [309] | Wolfram S (1986a) Cryptography with cellular automata. In: Advances in cryptology—Crypto’85, vol 218. Springer, pp 429-432 |
| [310] | Wolfram, S., Random sequence generation by cellular automata, Adv Appl Math, 7, 2, 123-169 (1986) · Zbl 0603.68053 |
| [311] | Wolfram S (1994) Cellular automata and complexity-collected papers. Westview Press · Zbl 0823.68003 |
| [312] | Wolfram, S., A new kind of science (2002), Champaign: Wolfram-Media, Champaign · Zbl 1022.68084 |
| [313] | Wongthanavasu, S.; Sadananda, R., A ca-based edge operator and its performance evaluation, J Vis Commun Image Represent, 14, 2, 83-96 (2003) |
| [314] | Wuensche A (1994) Complexity in one-D cellular automata: gliders, basins of attraction and the z parameter. Working papers 94-04-025, Santa Fe Institute |
| [315] | Wuensche A (1998) Classifying cellular automata automatically. Santa Fe Institute Working Paper 98-02-018 |
| [316] | Wuensche A (2017) Discrete dynamics lab. http://www.ddlab.com/. Accessed Aug 25, 2017 |
| [317] | Xiao, X.; Shao, S.; Huang, Z.; Chou, K., Using pseudo amino acid composition to predict protein structural classes: approached with complexity measure factor, J Comput Chem, 27, 4, 478-482 (2006) |
| [318] | Yang XS, Yang YZ (2007) Cellular automata networks. In: Proceedings of unconventional computing. Luniver Press, pp 280-302 |
| [319] | Ye R, Li H (2008) A novel image scrambling and watermarking scheme based on cellular automata. In: Proceedings of international symposium on electronic commerce and security, pp 938-941 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
