{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T01:40:01Z","timestamp":1779154801579,"version":"3.51.4"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2110,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004527_inline01\"\/>Kolmogorov complexity of its (<jats:italic>n<\/jats:italic>\u00d7<jats:italic>n<\/jats:italic>)-squares. We construct tile sets for which this bound is tight: all (<jats:italic>n<\/jats:italic>\u00d7<jats:italic>n<\/jats:italic>)-squares in all tilings have complexity \u03a9(<jats:italic>n<\/jats:italic>). This adds a quantitative angle to classical results on non-recursivity of tilings\u2014that we also develop in terms of Turing degrees of unsolvability.<\/jats:p>","DOI":"10.2178\/jsl\/1208359062","type":"journal-article","created":{"date-parts":[[2008,4,16]],"date-time":"2008-04-16T19:50:47Z","timestamp":1208375447000},"page":"593-613","source":"Crossref","is-referenced-by-count":27,"title":["Complex tilings"],"prefix":"10.1017","volume":"73","author":[{"given":"Bruno","family":"Durand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid A.","family":"Levin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200004527_ref021","first-page":"23","volume-title":"Proceedings of the Symposium on Mathematical Theory of Automata","author":"Wang","year":"1962"},{"key":"S0022481200004527_ref004","volume-title":"STACS'00","volume":"1770","author":"Cervelle","year":"2000"},{"key":"S0022481200004527_ref012","doi-asserted-by":"publisher","DOI":"10.1142\/9789814503532_0007"},{"key":"S0022481200004527_ref008","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004823720305"},{"key":"S0022481200004527_ref006","doi-asserted-by":"crossref","first-page":"732","DOI":"10.1145\/380752.380880","volume-title":"STOC","author":"Durand","year":"2001"},{"key":"S0022481200004527_ref014","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxh124"},{"key":"S0022481200004527_ref013","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"S0022481200004527_ref020","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1961.tb03975.x"},{"key":"S0022481200004527_ref011","first-page":"283","volume":"39","author":"Hanf","year":"1974","journal-title":"Nonrecursive tilings of the plane. I"},{"key":"S0022481200004527_ref016","unstructured":"Muchnik Andrej , personal communication, 2000."},{"key":"S0022481200004527_ref001","first-page":"407","volume-title":"Appendix A: \u201cTiling problems\u201d","author":"Allauzen","year":"1996"},{"key":"S0022481200004527_ref002","volume-title":"The undecidability of the domino problem","volume":"66","author":"Berger","year":"1966"},{"key":"S0022481200004527_ref003","volume-title":"The classical decision problem","author":"B\u00f6rger","year":"1996"},{"key":"S0022481200004527_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00027-4"},{"key":"S0022481200004527_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BF02984815"},{"key":"S0022481200004527_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90007-R"},{"key":"S0022481200004527_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/BF00971620"},{"key":"S0022481200004527_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"S0022481200004527_ref017","first-page":"286","volume":"39","author":"Myers","year":"1974","journal-title":"Nonrecursive tilings of the plane, ii"},{"key":"S0022481200004527_ref018","volume-title":"Classical recursion theory","author":"Odifreddi","year":"1989"},{"key":"S0022481200004527_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/BF01418780"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200004527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T19:54:35Z","timestamp":1684353275000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200004527\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["S0022481200004527"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1208359062","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}