{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:42Z","timestamp":1760202762979},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319731162"},{"type":"electronic","value":"9783319731179"}],"license":[{"start":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T00:00:00Z","timestamp":1513900800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-73117-9_16","type":"book-chapter","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T16:45:34Z","timestamp":1513874734000},"page":"227-238","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Conjugacy of One-Dimensional One-Sided Cellular Automata is Undecidable"],"prefix":"10.1007","author":[{"given":"Joonatan","family":"Jalonen","sequence":"first","affiliation":[]},{"given":"Jarkko","family":"Kari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"key":"16_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.: Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J. Comput. Syst. Sci. 6, 448\u2013464 (1972)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"16_CR2","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1016\/S0019-3577(00)87901-X","volume":"10","author":"M Boyle","year":"1999","unstructured":"Boyle, M., Kitchens, B.: Periodic points for onto cellular automata. Indag. Math. 10(4), 483\u2013493 (1999)","journal-title":"Indag. Math."},{"issue":"4","key":"16_CR3","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1137\/0218057","volume":"18","author":"K Culik II","year":"1989","unstructured":"Culik II, K., Pachl, J., Yu, S.: On the limit sets of cellular automata. SIAM J. Comput. 18(4), 831\u2013842 (1989)","journal-title":"SIAM J. Comput."},{"key":"16_CR4","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/S0304-3975(03)00290-1","volume":"304","author":"P Dartnell","year":"2003","unstructured":"Dartnell, P., Maass, A., Schwartz, F.: Combinatorial constructions associated to the dynamics of one-sided cellular automata. Theoret. Comput. Sci. 304, 485\u2013497 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR5","unstructured":"Di Lena, P.: Decidable and computational properties of cellular automata. Department of Computer Science, University of Bologna, Ph.D. thesis (2007)"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-662-47221-7_8","volume-title":"Cellular Automata and Discrete Complex Systems","author":"J Epperlein","year":"2015","unstructured":"Epperlein, J.: Classification of elementary cellular automata up to topological conjugacy. In: Kari, J. (ed.) AUTOMATA 2015. LNCS, vol. 9099, pp. 99\u2013112. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47221-7_8"},{"key":"16_CR7","unstructured":"Epperlein, J.: Topological conjugacies between cellular automata. Fakult\u00e4t Mathematik und Naturwissenschaften der Technischen Universit\u00e4t Dresden, Ph.D. thesis (2017)"},{"key":"16_CR8","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1017\/S0143385700006738","volume":"12","author":"LP Hurd","year":"1992","unstructured":"Hurd, L.P., Kari, J., Culik, K.: The topological entropy of cellular automata is uncomputable. Ergod. Theory Dyn. Syst. 12, 255\u2013265 (1992)","journal-title":"Ergod. Theory Dyn. Syst."},{"key":"16_CR9","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1137\/0221036","volume":"21","author":"J Kari","year":"1992","unstructured":"Kari, J.: The nilpotency problem of one-dimensional cellular automata. SIAM J. Comput. 21, 571\u2013586 (1992)","journal-title":"SIAM J. Comput."},{"key":"16_CR10","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.: Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48, 149\u2013182 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR11","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.: Theory of cellular automata: a survey. Theoret. Comput. Sci. 334, 3\u201333 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR12","series-title":"Natural Computing Series","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/978-3-540-88869-7_32","volume-title":"Algorithmic Bioprocesses","author":"J Kari","year":"2009","unstructured":"Kari, J., Lukkarila, V.: Some undecidable dynamical properties for one-dimensional reversible cellular automata. In: Condon, A., Harel, D., Kok, J., Salomaa, A., Winfree, E. (eds.) Algorithmic Bioprocesses. NCS, pp. 639\u2013660. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-540-88869-7_32"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-540-85238-4_34","volume-title":"Mathematical Foundations of Computer Science 2008","author":"J Kari","year":"2008","unstructured":"Kari, J., Ollinger, N.: Periodicity and immortality in reversible computing. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 419\u2013430. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85238-4_34"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"K\u016frka, P.: Topological and Symbolic Dynamics, vol. 11. Soci\u00e9t\u00e9 Math\u00e9matique de France (2003)","DOI":"10.1515\/dmvm-2003-0028"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"9246","DOI":"10.1007\/978-0-387-30440-3_556","volume-title":"Encyclopedia of Complexity and System Sciences","author":"P K\u016frka","year":"2009","unstructured":"K\u016frka, P.: Topological dynamics of cellular automata. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and System Sciences, pp. 9246\u20139268. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-0-387-30440-3_556 . Print ISBN 978-0-387-75888-6"},{"issue":"3","key":"16_CR16","doi-asserted-by":"crossref","first-page":"519","DOI":"10.2307\/2272894","volume":"39","author":"S Aanderaa","year":"1974","unstructured":"Aanderaa, S., Lewis, H.: Linear sampling and the $$\\forall \\exists \\forall $$ \u2200 \u2203 \u2200 case of the decision problem. J. Symb. Logic 39(3), 519\u2013548 (1974)","journal-title":"J. Symb. Logic"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Nasu, M.: Textile systems for Endomorphisms and Automorphisms of the Shift, vol. 546. Memoirs of the American Mathematical Society (1995)","DOI":"10.1090\/memo\/0546"},{"key":"16_CR18","doi-asserted-by":"crossref","first-page":"120","DOI":"10.2307\/1970908","volume":"98","author":"RF Williams","year":"1973","unstructured":"Williams, R.F.: Classification of subshifts of finite type. Ann. Math. 98, 120\u2013153 (1973)","journal-title":"Ann. Math."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2018: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73117-9_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T11:45:00Z","timestamp":1570535100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-73117-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,22]]},"ISBN":["9783319731162","9783319731179"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73117-9_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017,12,22]]}}}