Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.40
URN: urn:nbn:de:0030-drops-102798
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10279/
Jeandel, Emmanuel ; Vanier, Pascal
A Characterization of Subshifts with Computable Language
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{jeandel_et_al:LIPIcs:2019:10279,
author = {Emmanuel Jeandel and Pascal Vanier},
title = {{A Characterization of Subshifts with Computable Language}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {40:1--40:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-100-9},
ISSN = {1868-8969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10279},
doi = {10.4230/LIPIcs.STACS.2019.40},
annote = {Keywords: subshifts, computability, Enumeration degree, Turing degree, minimal subshifts}
}
| Keywords: | subshifts, computability, Enumeration degree, Turing degree, minimal subshifts | |
| Seminar: | 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 12.03.2019 |
