2026-08-10T12:10:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9132 2024-03-06T10:43:26Z ddc:004 open_access

Aperiodic Points in Z²-subshifts Grandjean, Anael Hellouin de Menibus, Benjamin Vanier, Pascal Subshifts of finite type Wang tiles periodicity aperiodicity computability tilings We consider the structure of aperiodic points in Z^2-subshifts, and in particular the positions at which they fail to be periodic. We prove that if a Z^2-subshift contains points whose smallest period is arbitrarily large, then it contains an aperiodic point. This lets us characterise the computational difficulty of deciding if an Z^2-subshift of finite type contains an aperiodic point. Another consequence is that Z^2-subshifts with no aperiodic point have a very strong dynamical structure and are almost topologically conjugate to some Z-subshift. Finally, we use this result to characterize sets of possible slopes of periodicity for Z^3-subshifts of finite type. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anael Grandjean and Benjamin Hellouin de Menibus and Pascal Vanier 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.128 urn:nbn:de:0030-drops-91323 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.128 eng https://creativecommons.org/licenses/by/3.0/legalcode