{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T09:29:44Z","timestamp":1784021384629,"version":"3.55.0"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,6,23]],"date-time":"2018-06-23T00:00:00Z","timestamp":1529712000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100005877","name":"Luonnontieteiden ja Tekniikan Tutkimuksen Toimikunta","doi-asserted-by":"crossref","award":["296018"],"award-info":[{"award-number":["296018"]}],"id":[{"id":"10.13039\/501100005877","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["New Gener. Comput."],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00354-018-0034-6","type":"journal-article","created":{"date-parts":[[2018,6,23]],"date-time":"2018-06-23T06:12:07Z","timestamp":1529734327000},"page":"145-172","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0670-6138","authenticated-orcid":false,"given":"Jarkko","family":"Kari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,6,23]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Kari, J.: Reversible cellular automata. Developments in language theory. Lecture Notes in Computer Science, vol. 3572, pp. 57\u201368. Springer, Berlin (2005)","DOI":"10.1007\/11505877_5"},{"issue":"1\u20133","key":"34_CR2","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.: Theory of cellular automata: a survey. Theoret. Comput. Sci. 334(1\u20133), 3\u201333 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"34_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.tcs.2008.01.041","volume":"395","author":"K Morita","year":"2008","unstructured":"Morita, K.: Reversible computing and cellular automata\u2013a survey. Theoret. Comput. Sci. 395(1), 101\u2013131 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"34_CR4","volume-title":"Theory of Reversible Computing, Monographs in Theoretical Computer Science, An EATCS Series","author":"K Morita","year":"2017","unstructured":"Morita, K.: Theory of Reversible Computing, Monographs in Theoretical Computer Science, An EATCS Series. Springer, New York (2017)"},{"issue":"4","key":"34_CR5","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/BF01691062","volume":"3","author":"GA Hedlund","year":"1969","unstructured":"Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical systems. Math. Syst. Theory 3(4), 320\u2013375 (1969)","journal-title":"Math. Syst. Theory"},{"issue":"5","key":"34_CR6","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/S0022-0000(72)80009-6","volume":"6","author":"D Richardson","year":"1972","unstructured":"Richardson, D.: Tessellations with local transformations. J. Comput. Syst. Sci. 6(5), 373\u2013388 (1972)","journal-title":"J. Comput. Syst. Sci."},{"key":"34_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1090\/psapm\/014\/9961","volume":"14","author":"EF Moore","year":"1963","unstructured":"Moore, E.F.: Machine models of self-reproduction. Proc. Symp. Appl. Math. 14, 17\u201333 (1963)","journal-title":"Proc. Symp. Appl. Math."},{"key":"34_CR8","first-page":"685","volume":"14","author":"J Myhill","year":"1963","unstructured":"Myhill, J.: The converse to Moore\u2019s garden-of-eden theorem. Proc. Am. Math. Soc. 14, 685\u2013686 (1963)","journal-title":"Proc. Am. Math. Soc."},{"key":"34_CR9","unstructured":"Berlekamp, E., Conway, J., Guy, R.: Winning Ways, for Your Mathematical Plays: Games in Particular. vol. 2. Academic (1982)"},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"Gardner, M.: Mathematical games: The fantastic combinations of John Conway\u2019s new solitaire game \u201clife\u201d. Scientific American 223, 120\u2013123 (1970)","DOI":"10.1038\/scientificamerican1070-120"},{"key":"34_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14034-1","volume-title":"Cellular Automata and Groups. Springer Monographs in Mathematics","author":"T Ceccherini-Silberstein","year":"2010","unstructured":"Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Berlin (2010)"},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"Gottschalk, W.: Some general dynamical notions. In: Recent Advances in Topological Dynamics, Lecture Notes in Mathematics, vol. 318, pp. 120\u2013125. Springer, New York (1973)","DOI":"10.1007\/BFb0061728"},{"key":"34_CR13","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.tcs.2011.12.037","volume":"429","author":"J Kari","year":"2012","unstructured":"Kari, J.: Universal pattern generation by cellular automata. Theoret. Comput. Sci. 429, 180\u2013184 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"34_CR14","first-page":"758","volume":"72","author":"K Morita","year":"1989","unstructured":"Morita, K., Harao, M.: Computation universality of one-dimensional reversible (injective) cellular automata. IEICE Trans. E 72(6), 758\u2013762 (1989)","journal-title":"IEICE Trans. E"},{"issue":"1","key":"34_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01201813","volume":"29","author":"J Kari","year":"1996","unstructured":"Kari, J.: Representation of reversible cellular automata with block permutations. Math. Syst. Theory 29(1), 47\u201361 (1996)","journal-title":"Math. Syst. Theory"},{"issue":"1\u20132","key":"34_CR16","doi-asserted-by":"crossref","first-page":"93","DOI":"10.3233\/FI-1999-381208","volume":"38","author":"J Kari","year":"1999","unstructured":"Kari, J.: On the circuit depth of structurally reversible cellular automata. Fundamenta Informaticae 38(1\u20132), 93\u2013107 (1999)","journal-title":"Fundamenta Informaticae"},{"key":"34_CR17","doi-asserted-by":"crossref","unstructured":"Toffoli, T., Margolus, N.: Invertible cellular automata: a review. Phys. D 45, 229\u2013253 (1990)","DOI":"10.1016\/0167-2789(90)90185-R"},{"issue":"1","key":"34_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0167-2789(84)90252-5","volume":"10","author":"N Margolus","year":"1984","unstructured":"Margolus, N.: Physics-like models of computation. Phys. D Nonlinear Phenom. 10(1), 81\u201395 (1984)","journal-title":"Phys. D Nonlinear Phenom."},{"key":"34_CR19","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1103\/PhysRevLett.31.276","volume":"31","author":"J Hardy","year":"1973","unstructured":"Hardy, J., Pomeau, Y., de Pazzis, O.: Time evolution of a two-dimensional classical lattice system. Phys. Rev. Lett. 31, 276\u2013279 (1973)","journal-title":"Phys. Rev. Lett."},{"issue":"1\u20132","key":"34_CR20","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0167-2789(84)90253-7","volume":"10","author":"GY Vichniac","year":"1984","unstructured":"Vichniac, G.Y.: Simulating physics with cellular automata. Phys. D Nonlinear Phenom. 10(1\u20132), 96\u2013116 (1984)","journal-title":"Phys. D Nonlinear Phenom."},{"issue":"5","key":"34_CR21","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(72)80013-8","volume":"6","author":"S Amoroso","year":"1972","unstructured":"Amoroso, S., Patt, Y.N.: Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J. Comput. Syst. Sci. 6(5), 448\u2013464 (1972)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"34_CR22","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0167-2789(90)90195-U","volume":"45","author":"J Kari","year":"1990","unstructured":"Kari, J.: Reversibility of 2D cellular automata is undecidable. Phys. D Nonlinear Phenom. 45(1), 379\u2013385 (1990)","journal-title":"Phys. D Nonlinear Phenom."},{"issue":"1","key":"34_CR23","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.: Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48(1), 149\u2013182 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"34_CR24","first-page":"19","volume":"5","author":"K Sutner","year":"1991","unstructured":"Sutner, K.: De Bruijn graphs and linear cellular automata. Complex Syst. 5(1), 19\u201330 (1991)","journal-title":"Complex Syst."},{"key":"34_CR25","unstructured":"Czeizler, E., Kari, J.: A tight linear bound on the neighborhood of inverse cellular automata. In: Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, pp. 410\u2013420 (2005)"},{"key":"34_CR26","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/978-3-642-20712-9_17","volume-title":"Computer Science\u2014Theory and Applications","author":"J Kari","year":"2011","unstructured":"Kari, J.: Snakes and cellular automata: Reductions and inseparability results. In: Kulikov, A., Vereshchagin, N. (eds.) Computer Science\u2014Theory and Applications, pp. 223\u2013232. Springer, Berlin (2011)"},{"key":"34_CR27","doi-asserted-by":"crossref","unstructured":"Boyle, M.: Open problems in symbolic dynamics. Geometric and Probabilistic Structures in Dynamics. Contemporary Mathematics, vol. 469, pp. 69\u2013118. American Mathematical Society, Providence (2008)","DOI":"10.1090\/conm\/469\/09161"},{"key":"34_CR28","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.) Mathematical Foundations of Computer Science 2008, pp. 419\u2013430. Springer, Berlin (2008)"},{"key":"34_CR29","doi-asserted-by":"crossref","unstructured":"Delacourt, M., Ollinger, N.: Permutive one-way cellular automata and the finiteness problem for automaton groups. In: J.\u00a0Kari, F.\u00a0Manea, I.\u00a0Petre (eds.) Unveiling Dynamics and Complexity, pp. 234\u2013245. Springer International Publishing (2017)","DOI":"10.1007\/978-3-319-58741-7_23"},{"key":"34_CR30","doi-asserted-by":"crossref","unstructured":"Cook, M.: Universality in elementary cellular automata. Complex Syst. 15(1) (2004)","DOI":"10.25088\/ComplexSystems.15.1.1"},{"issue":"6","key":"34_CR31","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"CH Bennett","year":"1973","unstructured":"Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525\u2013532 (1973)","journal-title":"IBM J. Res. Dev."},{"key":"34_CR32","unstructured":"Lecerf, Y.: Machines de Turing r\u00e9versibles. R\u00e9cursive insolubilit\u00e9 en $$n\\in {N}$$ n \u2208 N de l\u2019\u00e9quation $$u=\\theta ^n u$$ u = \u03b8 n u , o\u00f9 $$\\theta$$ \u03b8 est un \u201cisomorphisme de code\u201d. Comptes Rendus Hebdomadaires des S\u00e9ances de l\u2019Acad\u00e9mie des Sciences 257, 2597\u20132600 (1963)"},{"issue":"2","key":"34_CR33","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0304-3975(96)00081-3","volume":"168","author":"K Morita","year":"1996","unstructured":"Morita, K.: Universality of a reversible two-counter machine. Theoret. Comput. Sci. 168(2), 303\u2013320 (1996)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"34_CR34","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0022-0000(77)80007-X","volume":"15","author":"T Toffoli","year":"1977","unstructured":"Toffoli, T.: Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15(2), 213\u2013231 (1977)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"34_CR35","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0304-3975(95)00038-X","volume":"148","author":"K Morita","year":"1995","unstructured":"Morita, K.: Reversible simulation of one-dimensional irreversible cellular automata. Theoret. Comput. Sci. 148(1), 157\u2013163 (1995)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"34_CR36","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1142\/S0129054195000202","volume":"6","author":"JC Dubacq","year":"1995","unstructured":"Dubacq, J.C.: How to simulate Turing machines by invertible one-dimensional cellular automata. Int. J. Found. Comput. Sci. 6(4), 395\u2013402 (1995)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"34_CR37","doi-asserted-by":"crossref","unstructured":"Delorme, M., Mazoyer, J., Ollinger, N., Theyssier, G.: Bulking i: An abstract theory of bulking. Theoretical Computer Science 412(30), 3866\u20133880 (2011) (Cellular Automata and Discrete Complex Systems)","DOI":"10.1016\/j.tcs.2011.02.023"},{"key":"34_CR38","doi-asserted-by":"crossref","unstructured":"Delorme, M., Mazoyer, J., Ollinger, N., Theyssier, G.: Bulking ii: Classifications of cellular automata. Theoretical Computer Science 412(30), 3881\u20133905 (2011) (Cellular Automata and Discrete Complex Systems)","DOI":"10.1016\/j.tcs.2011.02.024"},{"key":"34_CR39","doi-asserted-by":"crossref","unstructured":"Ollinger, N.: Universalities in cellular automata. In: Rozenberg et\u00a0al. [54], pp. 189\u2013229","DOI":"10.1007\/978-3-540-92910-9_6"},{"key":"34_CR40","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-1-4471-0129-1_6","volume-title":"Collision-Based Computing","author":"J Durand-Lose","year":"2002","unstructured":"Durand-Lose, J.: Computing inside the billiard ball model. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 135\u2013160. Springer, London (2002)"},{"issue":"3","key":"34_CR41","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01857727","volume":"21","author":"E Fredkin","year":"1982","unstructured":"Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theoret. Phys. 21(3), 219\u2013253 (1982)","journal-title":"Int. J. Theoret. Phys."},{"key":"34_CR42","doi-asserted-by":"crossref","unstructured":"Durand-Lose, J.O.: Intrinsic universality of a 1-dimensional reversible cellular automaton. In: R.\u00a0Reischuk, M.\u00a0Morvan (eds.) STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, L\u00fcbeck, Germany, February 27 - March 1, 1997, Proceedings Lecture Notes in Computer Science, vol. 1200, pp. 439\u2013450. Springer (1997)","DOI":"10.1007\/BFb0023479"},{"key":"34_CR43","unstructured":"Janzing, D.: Is there a physically universal cellular automaton or hamiltonian? (2010)"},{"key":"34_CR44","doi-asserted-by":"crossref","unstructured":"Schaeffer, L.: A physically universal cellular automaton. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS \u201915, pp. 237\u2013246. ACM, New York (2015)","DOI":"10.1145\/2688073.2688107"},{"key":"34_CR45","doi-asserted-by":"crossref","unstructured":"Salo, V., T\u00f6rm\u00e4, I.: A one-dimensional physically universal cellular automaton. In: J.\u00a0Kari, F.\u00a0Manea, I.\u00a0Petre (eds.) Unveiling Dynamics and Complexity, pp. 375\u2013386. Springer International Publishing (2017)","DOI":"10.1007\/978-3-319-58741-7_35"},{"key":"34_CR46","unstructured":"Moreira, A., Gajardo, A.: Time-symmetric cellular automata. In: J.\u00a0Kari (ed.) Proceedings of JAC 2010, Journ\u00e9es Automates Cellulaires, pp. 180\u2013190. TUCS, Turku Centre for Computer Science (2010)"},{"issue":"4","key":"34_CR47","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1016\/j.jcss.2012.01.006","volume":"78","author":"A Gajardo","year":"2012","unstructured":"Gajardo, A., Kari, J., Moreira, A.: On time-symmetry in cellular automata. J. Comput. Syst. Sci. 78(4), 1115\u20131126 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"34_CR48","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0019-3577(93)90040-6","volume":"4","author":"MA Shereshevsky","year":"1993","unstructured":"Shereshevsky, M.A.: Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms. Indagationes Mathematicae 4(2), 203\u2013210 (1993)","journal-title":"Indagationes Mathematicae"},{"issue":"3","key":"34_CR49","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0167-2789(91)90150-8","volume":"49","author":"T Hattori","year":"1991","unstructured":"Hattori, T., Takesue, S.: Additive conserved quantities in discrete-time lattice dynamical systems. Phys. D Nonlinear Phenom. 49(3), 295\u2013322 (1991)","journal-title":"Phys. D Nonlinear Phenom."},{"issue":"4","key":"34_CR50","doi-asserted-by":"publisher","first-page":"1275","DOI":"10.1007\/s11047-010-9222-0","volume":"10","author":"E Formenti","year":"2011","unstructured":"Formenti, E., Kari, J., Taati, S.: On the hierarchy of conservation laws in a cellular automaton. Nat. Comput. 10(4), 1275\u20131294 (2011)","journal-title":"Nat. Comput."},{"issue":"5","key":"34_CR51","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1007\/s10955-015-1281-2","volume":"160","author":"J Kari","year":"2015","unstructured":"Kari, J., Taati, S.: Statistical mechanics of surjective cellular automata. J. Stat. Phys. 160(5), 1198\u20131243 (2015)","journal-title":"J. Stat. Phys."},{"key":"34_CR52","doi-asserted-by":"crossref","unstructured":"Kari, J., Taati, S.: Conservation laws and invariant measures in surjective cellular automata. In: N.\u00a0Fat\u00e8s, E.G. Chacc, A.\u00a0Maass, I.\u00a0Rapaport (eds.) AUTOMATA, Discrete Mathematics and Theoretical Computer Science Proceedings, vol.\u00a0AP, pp. 113\u2013122. DMTCS (2011)","DOI":"10.46298\/dmtcs.2968"},{"key":"34_CR53","doi-asserted-by":"crossref","unstructured":"Kari, J.: Basic concepts of cellular automata. In: Rozenberg, G., B\u00e4ck, T., Kok, J.N. (eds.) Handbook of Natural Computing, vol. 1, pp. 3\u201324. Springer, New York (2010)","DOI":"10.1007\/978-3-540-92910-9_1"},{"key":"34_CR54","unstructured":"K\u016frka, P.: Topological and Symbolic Dynamics. Collection SMF, Soci\u00e9t\u00e9 math\u00e9matique de France (2003)"},{"key":"34_CR55","doi-asserted-by":"crossref","unstructured":"Toffoli, T., Margolus, N.: Cellular Automata Machines: A New Environment for Modeling. MIT press (1987)","DOI":"10.7551\/mitpress\/1763.001.0001"},{"key":"34_CR56","doi-asserted-by":"crossref","unstructured":"Chopard, B., Droz, M.: Cellular Automata Modeling of Physical Systems. Cambridge University Press, Cambridge (1998)","DOI":"10.1017\/CBO9780511549755"}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00354-018-0034-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-018-0034-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-018-0034-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T08:19:10Z","timestamp":1751703550000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00354-018-0034-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,23]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["34"],"URL":"https:\/\/doi.org\/10.1007\/s00354-018-0034-6","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"value":"0288-3635","type":"print"},{"value":"1882-7055","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,23]]},"assertion":[{"value":"2 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}