2026-07-27T16:29:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6245 2024-03-06T10:37:52Z ddc:004 open_access

Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic Sablik, Mathieu Schraudner, Michael Subshift computability time complexity space complexity tilings Realization of d-dimensional effective subshifts as projective sub-actions of d + d'-dimensional sofic subshifts for d' >= 1 is now well known [Hochman, 2009; Durand/Romashchenko/Shen, 2012; Aubrun/Sablik, 2013]. In this paper we are interested in qualitative aspects of this realization. We introduce a new topological conjugacy invariant for effective subshifts, the speed of convergence, in view to exhibit algorithmic properties of these subshifts in contrast to the usual framework that focuses on undecidable properties. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mathieu Sablik and Michael Schraudner 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.110 urn:nbn:de:0030-drops-62454 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.110 eng https://creativecommons.org/licenses/by/3.0/legalcode