文章基本信息

标题：A Characterization of Subshifts with Computable Language
本地全文：下载
作者：Emmanuel Jeandel ; Pascal Vanier
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：126
页码：1-16
DOI：10.4230/LIPIcs.STACS.2019.40
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：subshifts; computability; Enumeration degree; Turing degree; minimal subshifts