2026-07-22T11:37:29Z https://drops.dagstuhl.de/oai

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

A Characterization of Subshifts with Computable Language Jeandel, Emmanuel Vanier, Pascal subshifts computability Enumeration degree Turing degree minimal subshifts Subshifts are sets of colorings of Z^d by a finite alphabet that avoid some family of forbidden patterns. We investigate here some analogies with group theory that were first noticed by the first author. In particular we prove several theorems on subshifts inspired by Higman’s embedding theorems of group theory, among which, the fact that subshifts with a computable language can be obtained as restrictions of minimal subshifts of finite type. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emmanuel Jeandel and Pascal Vanier 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.40 urn:nbn:de:0030-drops-102798 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.40 eng https://creativecommons.org/licenses/by/3.0/legalcode