2026-07-25T00:39:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22846 2025-10-02T13:35:21Z ddc:004 open_access

Computability of Extender Sets in Multidimensional Subshifts Callard, Antonin Paviet Salomon, Léo Vanier, Pascal Symbolic dynamics subshifts extender sets extender entropy computability sofic shifts tilings Subshifts are sets of colorings of ℤ^d defined by families of forbidden patterns. Given a subshift and a finite pattern, its extender set is the set of admissible completions of this pattern. It has been conjectured that the behavior of extender sets, and in particular their growth called extender entropy [French and Pavlov, 2019], could provide a way to separate the classes of sofic and effective subshifts. We prove here that both classes have the same possible extender entropies: exactly the Π₃ real numbers of [0,+∞). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antonin Callard and Léo Paviet Salomon and Pascal Vanier 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.21 urn:nbn:de:0030-drops-228462 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.21 eng https://creativecommons.org/licenses/by/4.0/legalcode