2026-07-23T00:29:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10262 2024-03-06T10:45:39Z ddc:004 open_access

Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts Destombes, Julien Romashchenko, Andrei Sofic shifts Block complexity Kolmogorov complexity We suggest necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity. Using this technique we provide examples of effective and non-sofic shifts on Z^2 with very low block complexity: the number of globally admissible patterns of size n x n grows only as a polynomial in n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julien Destombes and Andrei Romashchenko 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.23 urn:nbn:de:0030-drops-102624 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.23 eng https://creativecommons.org/licenses/by/3.0/legalcode