{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T12:31:54Z","timestamp":1771849914898,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540571827","type":"print"},{"value":"9783540479277","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57182-5_35","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:10:36Z","timestamp":1330258236000},"page":"433-441","source":"Crossref","is-referenced-by-count":4,"title":["Global properties of 2D cellular automata: some complexity results"],"prefix":"10.1007","author":[{"given":"Bruno","family":"Durand","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"35_CR1","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(72)80013-8","volume":"6","author":"S. Amoroso","year":"1972","unstructured":"S. Amoroso and Y.N. Patt. Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures. J. Comp. Syst. Sci., 6:448\u2013464, 1972.","journal-title":"J. Comp. Syst. Sci."},{"key":"35_CR2","doi-asserted-by":"crossref","unstructured":"R. Berger. The undecidability of the domino problem. Memoirs of the American Mathematical Society, 66, 1966.","DOI":"10.1090\/memo\/0066"},{"key":"35_CR3","unstructured":"J. Kari. Reversibility and surjectivity problems of cellular automata. to appear in Journal of Computer and System Sciences."},{"key":"35_CR4","first-page":"379","volume":"D 45","author":"J. Kari","year":"1990","unstructured":"J. Kari. Reversability of 2d cellular automata is undecidable. Physica, D 45:379\u2013385, 1990.","journal-title":"Physica"},{"key":"35_CR5","first-page":"13","volume":"14","author":"E. F. Moore","year":"1962","unstructured":"E.F. Moore. Machine models of self-reproduction. Proc. Symp. Apl. Math., 14:13\u201333, 1962.","journal-title":"Proc. Symp. Apl. Math."},{"key":"35_CR6","first-page":"685","volume":"14","author":"J. Myhill","year":"1963","unstructured":"J. Myhill. The converse to Moore's garden-of-eden theorem. Proc. Am. Math. Soc., 14:685\u2013686, 1963.","journal-title":"Proc. Am. Math. Soc."},{"key":"35_CR7","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/S0022-0000(72)80009-6","volume":"6","author":"D. Richardson","year":"1972","unstructured":"D. Richardson. Tesselations with local transformations. Journal of Computer and System Sciences, 6:373\u2013388, 1972.","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR8","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF01418780","volume":"12","author":"R. M. Robinson","year":"1971","unstructured":"R.M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12:177\u2013209, 1971.","journal-title":"Inventiones Mathematicae"},{"key":"35_CR9","first-page":"19","volume":"5","author":"K. Sutner","year":"1991","unstructured":"K. Sutner. De Bruijn graphs and linear cellular automata. Complex Systems, 5:19\u201330, 1991.","journal-title":"Complex Systems"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1993"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57182-5_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T00:59:30Z","timestamp":1619571570000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57182-5_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571827","9783540479277"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-57182-5_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]}}}