{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T13:28:30Z","timestamp":1790429310137,"version":"4.1.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"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":["grant 296018"],"award-info":[{"award-number":["grant 296018"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ANR project CoCoGro","award":["ANR-16-CE40-0005"],"award-info":[{"award-number":["ANR-16-CE40-0005"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we study colorings (or tilings) of the two-dimensional grid<jats:inline-formula><jats:alternatives><jats:tex-math>${\\mathbb {Z}}^{2}$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mrow><mml:mi>\u2124<\/mml:mi><\/mml:mrow><mml:mrow><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. A coloring is said to be valid with respect to a set<jats:italic>P<\/jats:italic>of<jats:italic>n<\/jats:italic>\u00d7<jats:italic>m<\/jats:italic>rectangular patterns if all<jats:italic>n<\/jats:italic>\u00d7<jats:italic>m<\/jats:italic>sub-patterns of the coloring are in<jats:italic>P<\/jats:italic>. A coloring<jats:italic>c<\/jats:italic>is said to be of low complexity with respect to a rectangle if there exist<jats:inline-formula><jats:alternatives><jats:tex-math>$m,n\\in \\mathbb {N}$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mi>\u2115<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and a set<jats:italic>P<\/jats:italic>of<jats:italic>n<\/jats:italic>\u00d7<jats:italic>m<\/jats:italic>rectangular patterns such that<jats:italic>c<\/jats:italic>is valid with respect to<jats:italic>P<\/jats:italic>and |<jats:italic>P<\/jats:italic>|\u2264<jats:italic>n<\/jats:italic><jats:italic>m<\/jats:italic>. Open since it was stated in 1997, Nivat\u2019s conjecture states that such a coloring is necessarily periodic. If Nivat\u2019s conjecture is true, all valid colorings with respect to<jats:italic>P<\/jats:italic>such that |<jats:italic>P<\/jats:italic>|\u2264<jats:italic>m<\/jats:italic><jats:italic>n<\/jats:italic>must be periodic. We prove that there exists at least one periodic coloring among the valid ones. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Then, we use our result to show that Nivat\u2019s conjecture holds for uniformly recurrent configurations. These results also extend to other convex shapes in place of the rectangle. After that, we prove that the<jats:italic>nm<\/jats:italic>bound is multiplicatively optimal for the decidability of the domino problem, as for all<jats:italic>\u03b5<\/jats:italic>&gt;\u20090 it is undecidable to determine if there exists a valid coloring for a given<jats:inline-formula><jats:alternatives><jats:tex-math>$m,n\\in \\mathbb {N}$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mi>\u2115<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and set of rectangular patterns<jats:italic>P<\/jats:italic>of size<jats:italic>n<\/jats:italic>\u00d7<jats:italic>m<\/jats:italic>such that |<jats:italic>P<\/jats:italic>|\u2264 (1 +<jats:italic>\u03b5<\/jats:italic>)<jats:italic>n<\/jats:italic><jats:italic>m<\/jats:italic>. We prove a slightly better bound in the case where<jats:italic>m<\/jats:italic>=<jats:italic>n<\/jats:italic>, as well as constructing aperiodic SFTs of pretty low complexity. This paper is an extended version of a paper published in STACS 2020 (Kari and Moutot 12).<\/jats:p>","DOI":"10.1007\/s00224-021-10063-8","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T02:02:26Z","timestamp":1635386546000},"page":"125-148","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Decidability and Periodicity of Low Complexity Tilings"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0670-6138","authenticated-orcid":false,"given":"Jarkko","family":"Kari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2073-4709","authenticated-orcid":false,"given":"Etienne","family":"Moutot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"10063_CR1","doi-asserted-by":"publisher","unstructured":"Baake, M., Grimm, U: Aperiodic order, Volume 1: A mathematical invitation. https:\/\/doi.org\/10.1017\/CBO9781139025256 (2014)","DOI":"10.1017\/CBO9781139025256"},{"key":"10063_CR2","doi-asserted-by":"crossref","unstructured":"Berger, R.: The undecidability of the domino problem. Memoirs of the american mathematical society american mathematical society (1966)","DOI":"10.1090\/memo\/0066"},{"key":"10063_CR3","unstructured":"Bhattacharya, S.: Periodicity and decidability of tilings of $\\mathbb {Z}^{2}$. https:\/\/muse.jhu.edu\/article\/746679\/summary (2016)"},{"key":"10063_CR4","doi-asserted-by":"publisher","first-page":"305","DOI":"10.24033\/bsmf.909","volume":"40","author":"GD Birkhoff","year":"1912","unstructured":"Birkhoff, G.D.: Quelques th\u00e9or\u00e8mes sur le mouvement des syst\u00e8mes dynamiques. Bull. Soc. Math. Fr. 40, 305\u2013323 (1912). https:\/\/doi.org\/10.24033\/bsmf.909","journal-title":"Bull. Soc. Math. Fr."},{"issue":"1","key":"10063_CR5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1090\/S0002-9947-97-01634-6","volume":"349","author":"M Boyle","year":"1997","unstructured":"Boyle, M., Lind, D.: Expansive subdynamics. Trans. Am. Math. Soc. 349(1), 55\u2013102 (1997). http:\/\/www.jstor.org\/stable\/2155304","journal-title":"Trans. Am. Math. Soc."},{"key":"10063_CR6","doi-asserted-by":"crossref","unstructured":"Cassaigne, J.: Subword complexity and periodicity in two or more dimensions. In: Grzegorz, R., Wolfgang, T. (eds.) Developments in Language Theory. Foundations, Applications, and Perspectives, 6-9 July 1999, pp 14\u201321. World Scientific, Aachen Germany (1999)","DOI":"10.1142\/9789812792464_0002"},{"key":"10063_CR7","doi-asserted-by":"crossref","unstructured":"Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Berlin Heidelberg (2010)","DOI":"10.1007\/978-3-642-14034-1"},{"issue":"9","key":"10063_CR8","doi-asserted-by":"publisher","first-page":"6487","DOI":"10.1090\/S0002-9947-2015-06391-0","volume":"367","author":"V Cyr","year":"2015","unstructured":"Cyr, V., Kra, B.: Nonexpansive $\\mathbb {Z}^{2}$-subdynamics and Nivat\u2019s Conjecture. Trans. Am. Math. Soc. 367(9), 6487\u20136537 (2015). https:\/\/doi.org\/10.1090\/s0002-9947-2015-06391-0","journal-title":"Trans. Am. Math. Soc."},{"key":"10063_CR9","unstructured":"Jeandel, E., Rao, M.: An aperiodic set of 11 wang tiles. https:\/\/www.advancesincombinatorics.com\/article\/18614-an-aperiodic-set-of-11-wang-tiles (2015)"},{"key":"10063_CR10","unstructured":"Jarkkom K.: Automata and Complexity. Essays presented to Eric Goles on the occasion of his 70th birthday. In: Adamatzky, A. (ed.) . in press. Springer Verlag (2021)"},{"key":"10063_CR11","doi-asserted-by":"publisher","unstructured":"Kari, J., Moutot, E.: Nivat\u2019s conjecture and pattern complexity in algebraic subshifts. Theor. Comput. Sci. https:\/\/doi.org\/10.1016\/j.tcs.2018.12.029 (2019)","DOI":"10.1016\/j.tcs.2018.12.029"},{"key":"10063_CR12","doi-asserted-by":"publisher","unstructured":"Kari, J., Moutot, E.: Decidability and periodicity of low complexity tilings. In: Paul, C., Bl\u00e4ser, M. (eds.) 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), volume 154 of Leibniz International Proceedings in Informatics (LIPIcs). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.14, pp 14:1\u201314:12. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020)","DOI":"10.4230\/LIPIcs.STACS.2020.14"},{"key":"10063_CR13","doi-asserted-by":"crossref","unstructured":"Kari, J., Szabados, M.: An algebraic geometric approach to nivat\u2019s conjecture. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, July 6-10, 2015, Proceedings, Part II, pp 273\u2013285. Springer, Kyoto, Japan (2015)","DOI":"10.1007\/978-3-662-47666-6_22"},{"key":"10063_CR14","unstructured":"Nivat, M.: Keynote address at the 25th anniversary of EATCS, during ICALP 1997 Bologna (1997)"},{"issue":"3","key":"10063_CR15","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01418780","volume":"12","author":"RM Robinson","year":"1971","unstructured":"Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12(3), 177\u2013209 (1971)","journal-title":"Invent. Math."},{"key":"10063_CR16","doi-asserted-by":"crossref","unstructured":"Sloane, N.J.A.: The on-line encyclopedia of integer sequences. http:\/\/oeis.org(2020)","DOI":"10.1515\/9780691197944-009"},{"key":"10063_CR17","doi-asserted-by":"crossref","unstructured":"Szabados, M.: Nivat\u2019s conjecture holds for sums of two periodic configurations. In: Tjoa, A.M., Bellatreche, L., Biffl, S., Leeuwen, J.v., Wiedermann, J. (eds.) SOFSEM 2018: Theory and Practice of Computer Science, pp 539\u2013551. Springer International Publishing, Cham (2018)","DOI":"10.1007\/978-3-319-73117-9_38"},{"key":"10063_CR18","doi-asserted-by":"publisher","unstructured":"Szegedy, M.: Algorithms to tile the infinite grid with finite clusters. In: 39th Annual Symposium on Foundations of Computer Science, FOCS \u201998, November 8-11, 1998. https:\/\/doi.org\/10.1109\/SFCS.1998.743437, pp 137\u2013147. IEEE Computer Society, Palo Alto, California, USA (1998)","DOI":"10.1109\/SFCS.1998.743437"},{"issue":"1","key":"10063_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/j.1538-7305.1961.tb03975.x","volume":"40","author":"H Wang","year":"1961","unstructured":"Wang, H.: Proving theorems by pattern recognition \u2013 II. Bell Syst. Tech. J. 40(1), 1\u201341 (1961). https:\/\/doi.org\/10.1002\/j.1538-7305.1961.tb03975.x","journal-title":"Bell Syst. Tech. J."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10063-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10063-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10063-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T22:34:57Z","timestamp":1726007697000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10063-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10063"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10063-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"24 September 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}