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.ICALP.2016.110
URN: urn:nbn:de:0030-drops-62454
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6245/
Sablik, Mathieu ;
Schraudner, Michael
Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic
Abstract
Realization of d-dimensional effective subshifts as projective sub-actions of d + d'-dimensional sofic subshifts for d' >= 1 is now well known [Hochman, 2009; Durand/Romashchenko/Shen, 2012; Aubrun/Sablik, 2013]. In this paper we are interested in qualitative aspects of this realization. We introduce a new topological conjugacy invariant for effective subshifts, the speed of convergence, in view to exhibit algorithmic properties of these subshifts in contrast to the usual framework that focuses on undecidable properties.
BibTeX - Entry
@InProceedings{sablik_et_al:LIPIcs:2016:6245,
author = {Mathieu Sablik and Michael Schraudner},
title = {{Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {110:1--110:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6245},
URN = {urn:nbn:de:0030-drops-62454},
doi = {10.4230/LIPIcs.ICALP.2016.110},
annote = {Keywords: Subshift, computability, time complexity, space complexity, tilings}
}
Keywords: |
|
Subshift, computability, time complexity, space complexity, tilings |
Collection: |
|
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
Issue Date: |
|
2016 |
Date of publication: |
|
23.08.2016 |