{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:04Z","timestamp":1725488524894},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_41","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T12:03:24Z","timestamp":1186056204000},"page":"491-502","source":"Crossref","is-referenced-by-count":2,"title":["Tilings: Recursivity and Regularity"],"prefix":"10.1007","author":[{"given":"Julien","family":"Cervelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Durand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"41_CR1","unstructured":"C. Allauzen and B. Durand. Appendix A: \u201cTiling problems\u201d. The classical decision problem (see [3]), pages 407\u2013420, 1996."},{"key":"41_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":"41_CR3","doi-asserted-by":"crossref","unstructured":"E. B\u00f6rger, E. Gr\u00e4del, and Y. Gurevich. The classical decision problem. Springer-Verlag, 1996.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"M. Delorme and J. Mazoyer, editors. Cellular automata: a Parallel model. Kluwer, 1999.","DOI":"10.1007\/978-94-015-9153-9"},{"key":"41_CR5","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/0304-3975(94)90244-5","volume":"134","author":"B. Durand","year":"1994","unstructured":"B. Durand. Inversion of 2d cellular automata: some complexity results. Theoretical Computer Science, 134:387\u2013401, 1994.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"41_CR6","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/S0022-0000(05)80077-7","volume":"49","author":"B. Durand","year":"1994","unstructured":"B. Durand. The surjectivity problem for 2D cellular automata. Journal of Computer and Systems Science, 49(3):718\u2013725, 1994.","journal-title":"Journal of Computer and Systems Science"},{"issue":"1","key":"41_CR7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0304-3975(94)00293-R","volume":"148","author":"B. Durand","year":"1995","unstructured":"B. Durand. A Random NP-complete problem for inversion of 2D cellular automata. Theoretical Computer Science, 148(1):19\u201332, 1995.","journal-title":"Theoretical Computer Science"},{"key":"41_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/3-540-63165-8_165","volume-title":"ICALP\u201997","author":"B. Durand","year":"1997","unstructured":"B. Durand. Tilings and quasiperiodicity. In ICALP\u201997, volume 1256 of Lecture Notes in Computer Science, pages 65\u201375. Springer Verlag, July 1997."},{"key":"41_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0304-3975(99)00027-4","volume":"221","author":"B. Durand","year":"1999","unstructured":"B. Durand. Tilings and quasiperiodicity. Theoretical Computer Science, 221:61\u201375, 1999.","journal-title":"Theoretical Computer Science"},{"key":"41_CR10","doi-asserted-by":"crossref","unstructured":"H. Furstenberg. Recurrence in ergodic theory and combinatorial number theory. Princetown University Press, 1981.","DOI":"10.1515\/9781400855162"},{"key":"41_CR11","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Y. Gurevich. Average case completeness. Journal of Computer and System Sciences, 42:346\u2013398, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"41_CR12","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/BF00971620","volume":"13","author":"Y. Gurevich","year":"1972","unstructured":"Y. Gurevich and I. Koriakov. A remark on Berger\u2019s paper on the domino problem. Siberian Journal of Mathematics, 13:459\u2013463, 1972. (in Russian).","journal-title":"Siberian Journal of Mathematics"},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"K. Ingersent. Matching rules for quasicrystalline tilings, pages 185\u2013212. World Scientific, 1991.","DOI":"10.1142\/9789814503532_0007"},{"key":"41_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80025-X","volume":"48","author":"J. Kari","year":"1994","unstructured":"J. Kari. Reversibility and surjectivity problems of cellular automata. Journal of Computer and System Sciences, 48:149\u2013182, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"41_CR15","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0304-3975(94)90041-8","volume":"127","author":"J. Kari","year":"1994","unstructured":"J. Kari. Rice\u2019s theorem for the limit set of cellular automata. Theoretical Computer Science, 127(2):229\u2013254, 1994.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"41_CR16","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"L. Levin. Average case complete problems. SIAM J. Comput, 15(1):285\u2013286, February 1986.","journal-title":"SIAM J. Comput"},{"key":"41_CR17","doi-asserted-by":"publisher","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":"41_CR18","unstructured":"P. van Embde Boas. Dominoes are forever. Research report 83-04, University of Amsterdam. Department of Mathematics., 1983."},{"key":"41_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/j.1538-7305.1961.tb03975.x","volume":"40","author":"H. Wang","year":"1961","unstructured":"H. Wang. Proving theorems by pattern recognition II. Bell System Technical Journal, 40:1\u201341, 1961.","journal-title":"Bell System Technical Journal"},{"key":"41_CR20","first-page":"23","volume-title":"Proc. Symp. on Mathematical Theory of Automata","author":"H. Wang","year":"1962","unstructured":"H. Wang. Dominoes and the \u2200\u2203\u2200-case of the decision problem. In Proc. Symp. on Mathematical Theory of Automata, pages 23\u201355. Brooklyn Polytechnic Institute, New York, 1962."}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T14:10:10Z","timestamp":1556719810000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}