LIPIcs.STACS.2009.1833.pdf
- Filesize: 195 kB
- 12 pages
Document
An Order on Sets of Tilings Corresponding to an Order on Languages
Authors
-
Part of:
Volume:
26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2009-02-19
Cite As Get BibTex
Nathalie Aubrun and Mathieu Sablik. An Order on Sets of Tilings Corresponding to an Order on Languages. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 99-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.STACS.2009.1833
Abstract
Traditionally a tiling is defined with a finite number of finite forbidden patterns. We can generalize this notion considering any set of patterns. Generalized tilings defined in this way can be studied with a dynamical point of view, leading to the notion of subshift. In this article we establish a correspondence between an order on subshifts based on dynamical transformations on them and an order on languages of forbidden patterns based on computability properties.
Subject Classification
Keywords
- Tiling
- Subshift
- Turing machine with oracle
- Subdynamics
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads