{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:58Z","timestamp":1760202598368},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540888680"},{"type":"electronic","value":"9783540888697"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-540-88869-7_32","type":"book-chapter","created":{"date-parts":[[2009,8,12]],"date-time":"2009-08-12T21:41:55Z","timestamp":1250113315000},"page":"639-660","source":"Crossref","is-referenced-by-count":9,"title":["Some Undecidable Dynamical Properties for\u00a0One-Dimensional Reversible Cellular Automata"],"prefix":"10.1007","author":[{"given":"Jarkko","family":"Kari","sequence":"first","affiliation":[]},{"given":"Ville","family":"Lukkarila","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,13]]},"reference":[{"key":"32_CR1","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\u00a0Comput Syst Sci"},{"key":"32_CR2","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"6","author":"CH Bennett","year":"1973","unstructured":"Bennett CH (1973) Logical reversibility of computation. IBM J\u00a0Res Dev 6:525\u2013532","journal-title":"IBM J\u00a0Res Dev"},{"key":"32_CR3","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":"32_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BF02760680","volume":"99","author":"F Blanchard","year":"1997","unstructured":"Blanchard F, Maass A (1997) Dynamical properties of expansive one-sided cellular automata. Israel J\u00a0Math 99:149\u2013174","journal-title":"Israel J\u00a0Math"},{"issue":"4","key":"32_CR5","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1142\/S0129054195000202","volume":"6","author":"J-C Dubacq","year":"1995","unstructured":"Dubacq J-C (1995) How to simulate any Turing machine by reversible one-dimensional cellular automaton. Int J\u00a0Found Comput Sci 6(4):395\u2013402","journal-title":"Int J\u00a0Found Comput Sci"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"Durand B, Formenti E, Varouchas G (2003) On undecidability of equicontinuity classification for cellular automata. Discrete Math Theor Comput Sci, pp\u00a0117\u2013128","DOI":"10.46298\/dmtcs.2302"},{"key":"32_CR7","doi-asserted-by":"publisher","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 Complex 14:210\u2013233","journal-title":"J Complex"},{"issue":"2","key":"32_CR8","doi-asserted-by":"publisher","first-page":"219","DOI":"10.2307\/2269811","volume":"31","author":"P Hooper","year":"1966","unstructured":"Hooper P (1966) The undecidability of the Turing machine immortality problem. J\u00a0Symbol Log 31(2):219\u2013234","journal-title":"J\u00a0Symbol Log"},{"key":"32_CR9","volume-title":"Introduction to automata theory, languages and computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft JE, Ullman JD (1979) Introduction to automata theory, languages and computation. Addison\u2013Wesley, Readings"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1137\/0221036","volume":"21","author":"J Kari","year":"1992","unstructured":"Kari J (1992) The nilpotency problem of one-dimensional cellular automata. SIAM J\u00a0Comput 21:571\u2013586","journal-title":"SIAM J\u00a0Comput"},{"key":"32_CR11","doi-asserted-by":"publisher","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\u00a0Comput Syst Sci"},{"key":"32_CR12","doi-asserted-by":"publisher","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 survey. Theor Comput Sci 334:3\u201333","journal-title":"Theor Comput Sci"},{"key":"32_CR13","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/978-3-540-85238-4_34","volume-title":"MFCS 2008","author":"J Kari","year":"2008","unstructured":"Kari J, Ollinger N (2008) Periodicity and immortality in reversible computing. In: MFCS 2008. Lecture notes in computer science, vol 5162. Springer, Berlin, pp\u00a0419\u2013430"},{"key":"32_CR14","series-title":"IMA volumes in mathematics and its applications","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/978-1-4613-0165-3_25","volume-title":"Codes, systems and graphical models","author":"P Kurka","year":"2001","unstructured":"Kurka P (2001) Topological dynamics of cellular automata. In: Markus B, Rosenthal J (eds) Codes, systems and graphical models. IMA volumes in mathematics and its applications, vol\u00a0123. Springer, Berlin, pp 447\u2013498"},{"key":"32_CR15","unstructured":"Lukkarila V (2008) Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata. J\u00a0Cell Autom (submitted)"},{"key":"32_CR16","doi-asserted-by":"publisher","first-page":"1516","DOI":"10.1016\/j.tcs.2008.12.006","volume":"410","author":"V Lukkarila","year":"2009","unstructured":"Lukkarila V (2009) The 4-way deterministic tiling problem is undecidable. Theor Comput Sci 410:1516\u20131533","journal-title":"Theor Comput Sci"},{"key":"32_CR17","volume-title":"Mathematical theory of computation","author":"Z Manna","year":"1974","unstructured":"Manna Z (1974) Mathematical theory of computation. McGraw\u2013Hill, New York"},{"key":"32_CR18","first-page":"758","volume":"E72","author":"K Morita","year":"1989","unstructured":"Morita K, Harao M (1989) Computation universality of one-dimensional reversible (injective) cellular automata. Trans IEICE Jpn E72:758\u2013762","journal-title":"Trans IEICE Jpn"},{"key":"32_CR19","series-title":"Mem Am Math Soc","volume-title":"Textile systems for endomorphisms and automorphisms of the shift","author":"M Nasu","year":"1995","unstructured":"Nasu M (1995) Textile systems for endomorphisms and automorphisms of the shift. Mem Am Math Soc, vol 546. AMS, Providence"},{"key":"32_CR20","doi-asserted-by":"publisher","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":"32_CR21","doi-asserted-by":"publisher","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 N S 4:203\u2013210","journal-title":"Indag Math N S"}],"container-title":["Natural Computing Series","Algorithmic Bioprocesses"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88869-7_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T09:27:11Z","timestamp":1685093231000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-88869-7_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783540888680","9783540888697"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88869-7_32","relation":{},"ISSN":["1619-7127"],"issn-type":[{"type":"print","value":"1619-7127"}],"subject":[],"published":{"date-parts":[[2009]]}}}