O2 Muu julkaisu
On Low Complexity Colorings of Grids
Tekijät: Kari, Jarkko
Toimittaja: Královič, Rastislav; Kučera, Antonin
Konferenssin vakiintunut nimi: Mathematical Foundations of Computer Science (MFCS)
Kustantaja: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Julkaisuvuosi: 2024
Journal: LIPICS – Leibniz international proceedings in informatics
Kokoomateoksen nimi: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Tietokannassa oleva lehden nimi: Leibniz International Proceedings in Informatics, LIPIcs
Sarjan nimi: LIPICS – Leibniz international proceedings in informatics
Vuosikerta: 306
ISBN: 978-3-95977-335-5
eISSN: 1868-8969
DOI: https://doi.org/10.4230/LIPIcs.MFCS.2024.3
Verkko-osoite: https://doi.org/10.4230/LIPIcs.MFCS.2024.3
Rinnakkaistallenteen osoite: 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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Julkaisussa olevat rahoitustiedot:
Academy of Finland project 354965
