{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T11:00:04Z","timestamp":1780743604478,"version":"3.54.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T00:00:00Z","timestamp":1687910400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T00:00:00Z","timestamp":1687910400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Turku (UTU) including Turku University Central Hospital"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study forced periodicity of two-dimensional configurations under certain constraints and use an algebraic approach to multidimensional symbolic dynamics in which <jats:italic>d<\/jats:italic>-dimensional configurations and finite patterns are presented as formal power series and Laurent polynomials, respectively, in <jats:italic>d<\/jats:italic> variables. We consider perfect colorings that are configurations such that the number of points of a given color in the neighborhood of any point depends only on the color of the point for some fixed relative neighborhood, and we show that by choosing the alphabet suitably any perfect coloring has a non-trivial annihilator, that is, there exists a Laurent polynomial whose formal product with the power series presenting the perfect coloring is zero. Using known results we obtain a sufficient condition for forced periodicity of two-dimensional perfect colorings. As corollaries of this result we get simple new proofs for known results of forced periodicity on the square and the triangular grids. Moreover, we obtain a new result concerning forced periodicity of perfect colorings in the king grid. We also consider perfect colorings of a particularly simple type: configurations that have low abelian complexity with respect to some shape, and we generalize a result that gives a sufficient condition for such configurations to be necessarily periodic. Also, some algorithmic aspects are considered.<\/jats:p>","DOI":"10.1007\/s00224-023-10127-x","type":"journal-article","created":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T04:02:27Z","timestamp":1687924947000},"page":"732-759","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Forced Periodicity of Perfect Colorings"],"prefix":"10.1007","volume":"67","author":[{"given":"Pyry","family":"Herva","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jarkko","family":"Kari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,6,28]]},"reference":[{"issue":"1","key":"10127_CR1","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(02)00744-6","volume":"268","author":"MA Axenovich","year":"2003","unstructured":"Axenovich, M.A.: On multiple coverings of the infinite rectangular grid with balls of constant radius. Discrete Mathematics 268(1), 31\u201348 (2003)","journal-title":"Discrete Mathematics"},{"key":"10127_CR2","series-title":"Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik","first-page":"61","volume-title":"25th International Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics (LIPIcs)","author":"A Ballier","year":"2008","unstructured":"Ballier, A., Durand, B., Jeandal, E.: Structural aspects of tilings. In: Albers, S., Weil, P. (eds.) 25th International Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, vol. 1, pp. 61\u201372. Dagstuhl, Germany (2008)"},{"key":"10127_CR3","doi-asserted-by":"publisher","unstructured":"Bhattacharya, S.: Periodicity and decidability of tilings of $$\\mathbb{Z} ^{2}$$. American Journal of Mathematics 142,(2016). https:\/\/doi.org\/10.1353\/ajm.2020.0006","DOI":"10.1353\/ajm.2020.0006"},{"key":"10127_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14034-1","volume-title":"Cellular Automata and Groups","author":"T Ceccherini-Silberstein","year":"2010","unstructured":"Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics, Springer, Berlin Heidelberg (2010)"},{"key":"10127_CR5","volume-title":"Covering Codes","author":"G Cohen","year":"1997","unstructured":"Cohen, G., Honkala, I., Litsyn, S., et al.: Covering Codes. Elsevier (1997)"},{"key":"10127_CR6","doi-asserted-by":"crossref","unstructured":"Cox DA, Little J, O\u2019Shea D (2015) Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer","DOI":"10.1007\/978-3-319-16721-3"},{"key":"10127_CR7","unstructured":"Geravker N, Puzynina SA (2021) Abelian Nivat\u2019s conjecture for non-rectangular patterns, arXiv:2111.04690"},{"key":"10127_CR8","first-page":"173","volume":"1","author":"C Godsil","year":"1993","unstructured":"Godsil, C.: Equitable partitions. Paul Erd\u00f6s is Eighty 1, 173\u2013192 (1993)","journal-title":"Paul Erd\u00f6s is Eighty"},{"key":"10127_CR9","unstructured":"Greenfeld R, Tao T (2021) The structure of translational tilings in $$\\mathbb{Z} ^d$$. Discrete Analysis"},{"key":"10127_CR10","unstructured":"Greenfeld R, Tao T (2022) A counterexample to the periodic tiling conjecture. 10.48550\/ARXIV.2211.15847, https:\/\/arxiv.org\/abs\/2211.15847"},{"key":"10127_CR11","volume-title":"Fundamentals of Domination in Graphs","author":"TW Haynes","year":"1997","unstructured":"Haynes, T.W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs, 1st edn. CRC Press (1997)","edition":"1"},{"key":"10127_CR12","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-031-05578-2_12","volume-title":"Developments in Language Theory","author":"E Heikkil\u00e4","year":"2022","unstructured":"Heikkil\u00e4, E., Herva, P., Kari, J.: On perfect coverings of two-dimensional grids. In: Diekert, V., Volkov, M. (eds.) Developments in Language Theory, pp. 152\u2013163. Springer International Publishing, Cham (2022)"},{"issue":"1","key":"10127_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2004.11.021","volume":"334","author":"J Kari","year":"2005","unstructured":"Kari, J.: Theory of cellular automata: A survey. Theoretical Computer Science 334(1), 3\u201333 (2005)","journal-title":"Theoretical Computer Science"},{"key":"10127_CR14","doi-asserted-by":"crossref","unstructured":"Kari J (2019) Low-complexity tilings of the plane. In: Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Lecture Notes in Computer Science, vol 11612. Springer, pp 35\u201345","DOI":"10.1007\/978-3-030-23247-4_2"},{"key":"10127_CR15","doi-asserted-by":"crossref","unstructured":"Kari J (2022) Expansivity and periodicity in algebraic subshifts, submitted for publication","DOI":"10.1007\/s00224-023-10139-7"},{"key":"10127_CR16","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.tcs.2018.12.029","volume":"777","author":"J Kari","year":"2019","unstructured":"Kari, J., Moutot, E.: Nivat\u2019s conjecture and pattern complexity in algebraic subshifts. Theoretical Computer Science 777, 379\u2013386 (2019)","journal-title":"Theoretical Computer Science"},{"key":"10127_CR17","doi-asserted-by":"crossref","unstructured":"Kari J, Szabados M (2015) An algebraic geometric approach to Nivat\u2019s conjecture. In: Proceedings of ICALP 2015, part II, pp 273\u2013285, http:\/\/dx.doi.org\/10.1007\/978-3-662-47666-6_22","DOI":"10.1007\/978-3-662-47666-6_22"},{"issue":"104","key":"10127_CR18","first-page":"481","volume":"271","author":"J Kari","year":"2020","unstructured":"Kari, J., Szabados, M.: An algebraic geometric approach to Nivat\u2019s conjecture. Information and Computation 271(104), 481 (2020)","journal-title":"Information and Computation"},{"key":"10127_CR19","unstructured":"Kurka P (2003) Topological and Symbolic Dynamics. Collection SMF, Soci\u00e9t\u00e9 math\u00e9matique de France, https:\/\/books.google.fi\/books?id=_TMZAQAAIAAJ"},{"key":"10127_CR20","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s002220050056","volume":"124","author":"JC Lagarias","year":"1996","unstructured":"Lagarias, J.C., Wang, Y.: Tiling the line with translates of one tile. Inventiones Mathematicae 124, 341\u2013365 (1996)","journal-title":"Inventiones Mathematicae"},{"key":"10127_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626302","volume-title":"An Introduction to Symbolic Dynamics and Coding","author":"D Lind","year":"1995","unstructured":"Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995)"},{"key":"10127_CR22","doi-asserted-by":"crossref","unstructured":"Lothaire M (1997) Combinatorics on Words, 2nd edn. Cambridge Mathematical Library, Cambridge University Press, 10.1017\/CBO9780511566097","DOI":"10.1017\/CBO9780511566097"},{"key":"10127_CR23","doi-asserted-by":"crossref","unstructured":"Moore EF (1962) Machine models of self-reproduction","DOI":"10.1090\/psapm\/014\/9961"},{"key":"10127_CR24","doi-asserted-by":"crossref","unstructured":"Morse M, Hedlund GA (1938) Symbolic dynamics. American Journal of Mathematics 60(4):815\u2013866. http:\/\/www.jstor.org\/stable\/2371264","DOI":"10.2307\/2371264"},{"key":"10127_CR25","doi-asserted-by":"crossref","unstructured":"Myhill JR (1963) The converse of Moore\u2019s Garden-of-Eden theorem","DOI":"10.2307\/2034301"},{"issue":"1","key":"10127_CR26","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0022-314X(77)90054-3","volume":"9","author":"D Newman","year":"1977","unstructured":"Newman, D.: Tesselation of integers. J Number Theory 9(1), 107\u2013111 (1977)","journal-title":"Tesselation of integers. J Number Theory"},{"key":"10127_CR27","unstructured":"Nivat M (1997) Invited talk at the 24th International Colloquium on Automata, Languages, and Programming (ICALP 1997)"},{"key":"10127_CR28","first-page":"283","volume":"5","author":"SA Puzynina","year":"2008","unstructured":"Puzynina, S.A.: Perfect colorings of radius $$r > 1$$ of the infinite rectangular grid. \u00c9lektron Mat Izv 5, 283\u2013292 (2008)","journal-title":"\u00c9lektron Mat Izv"},{"issue":"11","key":"10127_CR29","doi-asserted-by":"publisher","first-page":"1315","DOI":"10.1016\/j.ic.2009.03.005","volume":"207","author":"SA Puzynina","year":"2009","unstructured":"Puzynina, S.A.: On periodicity of generalized two-dimensional infinite words. Information and Computation 207(11), 1315\u20131328 (2009)","journal-title":"Information and Computation"},{"key":"10127_CR30","doi-asserted-by":"crossref","unstructured":"Puzynina SA (2019) Aperiodic two-dimensional words of small abelian complexity. The Electronic Journal of Combinatorics 26(4)","DOI":"10.37236\/8580"},{"key":"10127_CR31","doi-asserted-by":"crossref","unstructured":"Szegedy M (1998) Algorithms to tile the infinite grid with finite clusters. Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat No98CB36280) pp 137\u2013145","DOI":"10.1109\/SFCS.1998.743437"},{"issue":"1","key":"10127_CR32","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 - II. The Bell System Technical Journal 40(1), 1\u201341 (1961). https:\/\/doi.org\/10.1002\/j.1538-7305.1961.tb03975.x","journal-title":"The Bell System Technical Journal"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10127-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10127-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10127-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T10:09:00Z","timestamp":1691575740000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10127-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,28]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10127"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10127-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,28]]},"assertion":[{"value":"15 May 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}