{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T02:34:24Z","timestamp":1794364464644,"version":"4.9.0"},"publisher-location":"New York, NY","reference-count":31,"publisher":"Springer New York","isbn-type":[{"value":"9780387758886","type":"print"},{"value":"9780387304403","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-0-387-30440-3_552","type":"book-chapter","created":{"date-parts":[[2009,6,17]],"date-time":"2009-06-17T12:25:10Z","timestamp":1245241510000},"page":"9158-9172","source":"Crossref","is-referenced-by-count":2,"title":["Tiling Problem and Undecidability in Cellular Automata"],"prefix":"10.1007","author":[{"given":"Jarkko","family":"Kari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"552_CR1_552","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(72)80013-8","volume":"6","author":"S Amoroso","year":"1972","unstructured":"Amoroso S, Patt Y (1972) Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures. J\u00a0Comput Syst Sci 6:448\u2013464","journal-title":"J Comput Syst Sci"},{"key":"552_CR2_552","first-page":"1","volume":"66","author":"R Berger","year":"1966","unstructured":"Berger R (1966) The Undecidability of the Domino Problem. Mem Am Math Soc 66:1\u201372","journal-title":"Mem Am Math Soc"},{"key":"552_CR3_552","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0012-365X(96)00118-5","volume":"160","author":"KII Culik","year":"1996","unstructured":"Culik K II (1996) An aperiodic set of 13 Wang tiles. Discret Math 160: 245\u2013251","journal-title":"Discret Math"},{"key":"552_CR4_552","first-page":"177","volume":"2","author":"KII Culik","year":"1988","unstructured":"Culik K II, Yu S (1988) Undecidability of CA Classification Schemes. Complex Syst 2:177\u2013190","journal-title":"Complex Syst"},{"key":"552_CR5_552","doi-asserted-by":"crossref","unstructured":"Durand B, Formenti E, Varouchas G (2003) On undecidability of equicontinuity classification for cellular automata. In: Proceedings of Discrete Models for Complex Systems, Lyon, France, 16\u201319 June 2003, pp.\u00a0117\u2013128","DOI":"10.46298\/dmtcs.2302"},{"key":"552_CR6_552","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1006\/jcom.1998.0474","volume":"14","author":"M Finelli","year":"1998","unstructured":"Finelli M, Manzini G, Margara L (1998) Lyapunov Exponents versus Expansivity and Sensitivity in Cellular Automata. J\u00a0Complex 14:210\u2013233","journal-title":"J Complex"},{"key":"552_CR7_552","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF00971620","volume":"13","author":"YS Gurevich","year":"1972","unstructured":"Gurevich YS, Koryakov IO (1972) Remarks on Berger's paper on the domino problem. J\u00a0Sib Math J 13:319\u2013321","journal-title":"J Sib Math J"},{"key":"552_CR8_552","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1017\/S0143385700006738","volume":"12","author":"LP Hurd","year":"1992","unstructured":"Hurd LP, Kari J, Culik K (1992) The topological Entropy of Cellular Automata is Uncomputable. Ercodic Theor Dyn Syst 12:255\u2013265","journal-title":"Ercodic Theor Dyn Syst"},{"key":"552_CR9_552","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0167-2789(90)90195-U","volume":"45","author":"J Kari","year":"1990","unstructured":"Kari J (1990) Reversibility of 2D cellular automata is undecidable. Physica D 45:379\u2013385","journal-title":"Physica D"},{"key":"552_CR10_552","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1137\/0221036","volume":"21","author":"J Kari","year":"1992","unstructured":"Kari J (1992) The nilpotency problem of one\u2010dimensional cellular automata. SIAM J Comput 21:571\u2013586","journal-title":"SIAM J Comput"},{"key":"552_CR11_552","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80025-X","volume":"48","author":"J Kari","year":"1994","unstructured":"Kari J (1994) Reversibility and surjectivity problems of cellular automata. J\u00a0Comput Syst Sci 48:149\u2013182","journal-title":"J Comput Syst Sci"},{"key":"552_CR12_552","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0304-3975(94)90041-8","volume":"127","author":"J Kari","year":"1994","unstructured":"Kari J (1994) Rice's theorem for the Limit Sets of Cellular Automata. Theoret Comput Sci 127:229\u2013254","journal-title":"Theoret Comput Sci"},{"key":"552_CR13_552","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0012-365X(95)00120-L","volume":"160","author":"J Kari","year":"1996","unstructured":"Kari J (1996) A\u00a0small aperiodic set of Wang tiles. Discret Math 160:259\u2013264","journal-title":"Discret Math"},{"key":"552_CR14_552","unstructured":"Kari J (2008) Undecidable properties on the dynamics of reversible one\u2010dimensional cellular automata. In: Proceedings of Journ\u00e9es Automates Cellulaires, Uz\u00e9s, France, 21\u201325 April 2008"},{"key":"552_CR15_552","unstructured":"Kari J, Ollinger N Periodicity and immortality in reversible computing. (in press)"},{"key":"552_CR16_552","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s000390050090","volume":"9","author":"J Kari","year":"1999","unstructured":"Kari J, Papasoglu P (1999) Deterministic aperiodic tile sets. J\u00a0Geom Funct Anal 9:353\u2013369","journal-title":"J Geom Funct Anal"},{"key":"552_CR17_552","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1017\/S014338579706985X","volume":"17","author":"P Kurka","year":"1997","unstructured":"Kurka P (1997) Languages, equicontinuity and attractors in cellular automata. Ergod Theory Dyn Syst 17:417\u2013433","journal-title":"Ergod Theory Dyn Syst"},{"key":"552_CR18_552","unstructured":"Lukkarila V (2007) The 4\u2010way deterministic tiling problem is undecidable. (in press)"},{"key":"552_CR19_552","doi-asserted-by":"crossref","unstructured":"Moore EF (1962) Machine models of self\u2010reproduction. In: Proceedings of the Symposia in Applied Mathematics 14:17\u201333","DOI":"10.1090\/psapm\/014\/9961"},{"key":"552_CR20_552","first-page":"685","volume":"14","author":"J Myhill","year":"1963","unstructured":"Myhill J (1963) The Converse to Moore's Garden-of-Eden Theorem. In: Proceedings of the American Mathematical Society 14:685\u2013686","journal-title":"Proceedings of the American Mathematical Society"},{"key":"552_CR21_552","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF01418780","volume":"12","author":"RM Robinson","year":"1971","unstructured":"Robinson RM (1971) Undecidability and Nonperiodicity for Tilings of the plane. Invent Math 12:177\u2013209","journal-title":"Invent Math"},{"key":"552_CR22_552","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0019-3577(93)90040-6","volume":"4","author":"MA Shereshevsky","year":"1993","unstructured":"Shereshevsky MA (1993) Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms. Indag Math 4:203\u2013210","journal-title":"Indag Math"},{"key":"552_CR23_552","first-page":"107","volume":"3","author":"K Sutner","year":"1989","unstructured":"Sutner K (1989) A\u00a0note on the Culik-Yu classes. Complex Syst 3:107\u2013115","journal-title":"Complex Syst"},{"key":"552_CR24_552","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/j.1538-7305.1961.tb03975.x","volume":"40","author":"H Wang","year":"1961","unstructured":"Wang H (1961) Proving theorems by pattern recognition\u00a0\u2013 II. Bell Syst Techn J 40:1\u201342","journal-title":"Bell Syst Techn J"},{"key":"552_CR25_552","volume-title":"Cellular Automata","author":"EF Codd","year":"1968","unstructured":"Codd EF (1968) Cellular Automata. Academic Press, New York"},{"key":"552_CR26_552","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-77905-3","volume-title":"Models of massive parallelism: analysis of cellular automata and neural networks","author":"M Garzon","year":"1995","unstructured":"Garzon M (1995) Models of massive parallelism: analysis of cellular automata and neural networks. Springer, New York"},{"key":"552_CR27_552","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF01691062","volume":"3","author":"G Hedlund","year":"1969","unstructured":"Hedlund G (1969) Endomorphisms and automorphisms of shift dynamical systems. Math Syst Theory 3:320\u2013375","journal-title":"Math Syst Theory"},{"key":"552_CR28_552","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2004.11.021","volume":"334","author":"J Kari","year":"2005","unstructured":"Kari J (2005) Theory of cellular automata: a\u00a0survey. Theoret Comput Sci 334:3\u201333","journal-title":"Theoret Comput Sci"},{"key":"552_CR29_552","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1763.001.0001","volume-title":"Cellular Automata Machines","author":"T Toffoli","year":"1987","unstructured":"Toffoli T, Margolus N (1987) Cellular Automata Machines. MIT Press, Cambridge"},{"key":"552_CR30_552","volume-title":"Theory and Applications of Cellular Automata","year":"1986","unstructured":"Wolfram S (ed) (1986) Theory and Applications of Cellular Automata. World Scientific Press, Singapore"},{"key":"552_CR31_552","volume-title":"A New Kind of Science","author":"S Wolfram","year":"2002","unstructured":"Wolfram S (2002) A\u00a0New Kind of Science. Wolfram Media, Canada"}],"container-title":["Encyclopedia of Complexity and Systems Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30440-3_552","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T14:17:30Z","timestamp":1791987450000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30440-3_552"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9780387758886","9780387304403"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30440-3_552","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-0-387-30440-3","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2009]]}}}