{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T13:56:45Z","timestamp":1752674205918,"version":"3.37.3"},"reference-count":4,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["296018"],"award-info":[{"award-number":["296018"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"publisher","award":["IC1405","IC1405"],"award-info":[{"award-number":["IC1405","IC1405"]}],"id":[{"id":"10.13039\/501100000921","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["2608073211"],"award-info":[{"award-number":["2608073211"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>We study the problem of sequentializing a cellular automaton without introducing any intermediate states, and only performing reversible permutations on the tape. We give a decidable characterization of cellular automata which can be written as a single sweep of a bijective rule from left to right over an infinite tape. Such cellular automata are necessarily left-closing, and they move at least as much information to the left as they move information to the right.<\/jats:p>","DOI":"10.1007\/s11047-019-09745-7","type":"journal-article","created":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T15:14:11Z","timestamp":1559402051000},"page":"759-772","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Sequentializing cellular automata"],"prefix":"10.1007","volume":"19","author":[{"given":"Jarkko","family":"Kari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2059-194X","authenticated-orcid":false,"given":"Ville","family":"Salo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Worsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,1]]},"reference":[{"key":"9745_CR1","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/BF01691062","volume":"3","author":"GA Hedlund","year":"1969","unstructured":"Hedlund GA (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theory 3:320\u2013375","journal-title":"Math Syst Theory"},{"issue":"1","key":"9745_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01201813","volume":"29","author":"Jarkko Kari","year":"1996","unstructured":"Kari Jarkko (1996) Representation of reversible cellular automata with block permutations. Math Syst Theory 29(1):47\u201361","journal-title":"Math Syst Theory"},{"key":"9745_CR3","doi-asserted-by":"publisher","first-page":"3212","DOI":"10.1007\/978-1-4614-1800-9_199","volume-title":"Computational complexity","author":"P K\u016frka","year":"2012","unstructured":"K\u016frka P (2012) Topological dynamics of cellular automata. In: Meyers R (ed) Computational complexity. Springer, New York, pp 3212\u20133233"},{"key":"9745_CR4","volume-title":"Infinite words: automata, semigroups, logic and games","author":"D Perrin","year":"2004","unstructured":"Perrin D, Pin Jean-\u00c9ric (2004) Infinite words: automata, semigroups, logic and games, vol 141. Academic Press, Cambridge"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-019-09745-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11047-019-09745-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-019-09745-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T02:04:07Z","timestamp":1603850647000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11047-019-09745-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,1]]},"references-count":4,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["9745"],"URL":"https:\/\/doi.org\/10.1007\/s11047-019-09745-7","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2019,6,1]]},"assertion":[{"value":"1 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}