On Low Complexity Colorings of Grids
: Kari, Jarkko
: Královič, Rastislav; Kučera, Antonin
: Mathematical Foundations of Computer Science (MFCS)
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
: 2024
: LIPICS – Leibniz international proceedings in informatics
: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
: Leibniz International Proceedings in Informatics, LIPIcs
: LIPICS – Leibniz international proceedings in informatics
: 306
: 978-3-95977-335-5
: 1868-8969
DOI: https://doi.org/10.4230/LIPIcs.MFCS.2024.3
: https://doi.org/10.4230/LIPIcs.MFCS.2024.3
: https://research.utu.fi/converis/portal/detail/Publication/458652210
A d-dimensional configuration is a coloring of the infinite grid Zd using a finite number of colors. For a finite subset D ⊆ Zd, the D-patterns of a configuration are the patterns of shape D that appear in the configuration. A configuration is said to be admitted by these patterns. The number of distinct D-patterns in a configuration is a natural measure of its complexity. We focus on low complexity configurations, where the number of distinct D-patterns is at most |D|, the size of the shape. This framework includes the notorious open Nivat’s conjecture and the recently solved Periodic Tiling problem. We use algebraic tools to study the periodicity of low complexity configurations. In the two-dimensional case, if D ⊆ Z2 is a rectangle or any convex shape, we establish an algorithm to determine if a given collection of |D| patterns admits any configuration. This is based on the fact that if the given patterns admit a configuration, then they admit a periodic configuration. We also demonstrate that a two-dimensional low complexity configuration must be periodic if it originates from the well-known Ledrappier subshift or from several other algebraically defined subshifts.
:
Academy of Finland project 354965
UTU Research Portal