A1 Refereed original research article in a scientific journal

On Forced Periodicity of Perfect Colorings




AuthorsHerva Pyry, Kari Jarkko

PublisherSPRINGER

Publication year2023

JournalTheory of Computing Systems

Journal name in sourceTHEORY OF COMPUTING SYSTEMS

Journal acronymTHEOR COMPUT SYST

Number of pages28

ISSN1432-4350

eISSN1433-0490

DOIhttps://doi.org/10.1007/s00224-023-10127-x

Web address https://link.springer.com/article/10.1007/s00224-023-10127-x

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/180347487


Abstract

We study forced periodicity of two-dimensional configurations under certain constraints and use an algebraic approach to multidimensional symbolic dynamics in which d-dimensional configurations and finite patterns are presented as formal power series and Laurent polynomials, respectively, in d 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 showthat 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.


Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 13:01