Decidability and Periodicity of Low Complexity Tilings

Autor: Etienne Moutot, Jarkko Kari
Přispěvatelé: Department of Mathematics and Statistics, University of Turku, University of Turku, Calcul Naturel (CANA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), ANR-16-CE40-0005,CoCoGro,Calculabilité et combinatoire en dynamique symbolique sur des groupes.(2016)
Jazyk: angličtina
Rok vydání: 2019
Předmět:
FOS: Computer and information sciences
Symbolic dynamics Mathematics Subject Classification (2010) Mathematics of computing → Discrete mathematics
Discrete Mathematics (cs.DM)
37B50
2D subshifts
G.2.1
0102 computer and information sciences
Dynamical Systems (math.DS)
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Domino
Theory of computation → Computability
Theoretical Computer Science
Combinatorics
2012 ACM Subject Classification Mathematics of computing → Discrete mathematics
domino problem
symbolic dynamics
FOS: Mathematics
Nivat’s conjecture
Mathematics - Combinatorics
Rectangle
0101 mathematics
Mathematics - Dynamical Systems
Mathematics
Conjecture
010102 general mathematics
Regular polygon
decidability
Theory of computation → Computability phrases Nivat's conjecture
Undecidable problem
Decidability
F.4.3
low pattern complexity
Computational Theory and Mathematics
010201 computation theory & mathematics
Aperiodic graph
Theory of computation
Nivat's conjecture
Combinatorics (math.CO)
Computer Science - Discrete Mathematics
Zdroj: STACS 2020
STACS 2020, Mar 2020, Montpellier, France. ⟨10.4230/LIPIcs.STACS.2020.14⟩
Theory of Computing Systems
Theory of Computing Systems, Springer Verlag, 2021, ⟨10.1007/s00224-021-10063-8⟩
Theory of Computing Systems, 2021, ⟨10.1007/s00224-021-10063-8⟩
ISSN: 1432-4350
1433-0490
Popis: In this paper we study colorings (or tilings) of the two-dimensional grid $\mathbb{Z}^2$. A coloring is said to be valid with respect to a set $P$ of $n\times m$ rectangular patterns if all $n\times m$ sub-patterns of the coloring are in $P$. A coloring $c$ is said to be of low complexity with respect to a rectangle if there exist $m,n\in\mathbb{N}$ and a set $P$ of $n\times m$ rectangular patterns such that $c$ is valid with respect to $P$ and $|P|\leq nm$. Open since it was stated in 1997, Nivat's conjecture states that such a coloring is necessarily periodic. If Nivat's conjecture is true, all valid colorings with respect to $P$ such that $|P|\leq mn$ must be periodic. We prove that there exists at least one periodic coloring among the valid ones. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Then, we use our result to show that Nivat's conjecture holds for uniformly recurrent configurations. These results also extend to other convex shapes in place of the rectangle.\\ After that, we prove that the $nm$ bound is multiplicatively optimal for the decidability of the domino problem, as for all $\varepsilon>0$ it is undecidable to determine if there exists a valid coloring for a given $m,n\in \mathbb{N}$ and set of rectangular patterns $P$ of size $n\times m$ such that $|P|\leq (1+\varepsilon)nm$. We prove a slightly better bound in the case where $m=n$, as well as constructing aperiodic SFTs of pretty low complexity.\\ This paper is an extended version of a paper published in STACS 2020.
Extended version: new higher bounds on pattern complexity
Databáze: OpenAIRE
Externí odkaz: