License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10279/
Go to the corresponding LIPIcs Volume Portal

Jeandel, Emmanuel ; Vanier, Pascal

A Characterization of Subshifts with Computable Language

pdf-format:
LIPIcs-STACS-2019-40.pdf (0.7 MB)

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
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI