Other publication
On Low Complexity Colorings of Grids
Authors: Kari, Jarkko
Editors: Královič, Rastislav; Kučera, Antonin
Conference name: Mathematical Foundations of Computer Science (MFCS)
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication year: 2024
Journal: LIPICS – Leibniz international proceedings in informatics
Book title : 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Journal name in source: Leibniz International Proceedings in Informatics, LIPIcs
Series title: LIPICS – Leibniz international proceedings in informatics
Volume: 306
ISBN: 978-3-95977-335-5
eISSN: 1868-8969
DOI: https://doi.org/10.4230/LIPIcs.MFCS.2024.3
Web address : https://doi.org/10.4230/LIPIcs.MFCS.2024.3
Self-archived copy’s web address: 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.
Downloadable publication This is an electronic reprint of the original article. |  |
Funding information in the publication:
Academy of Finland project 354965
