@inproceedings{73c02e3ecb87477988a9ad63094636cc,
title = "A characterization of subshifts with computable language",
abstract = "Subshifts are sets of colorings of Zd 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{\textquoteright}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.",
keywords = "Computability, Enumeration degree, Minimal subshifts, Subshifts, Turing degree",
author = "Emmanuel Jeandel and Pascal Vanier",
note = "Publisher Copyright: {\textcopyright} Emmanuel Jeandel and Pascal Vanier.; 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019 ; Conference date: 13-03-2019 Through 16-03-2019",
year = "2019",
month = mar,
day = "1",
doi = "10.4230/LIPIcs.STACS.2019.40",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Rolf Niedermeier and Christophe Paul",
booktitle = "36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019",
}