 |
 |
|
|
| HAL: inria-00359625, version 1 |
| arXiv: 0902.1602 |
| See detailed view |  BibTeX,EndNote,... |
 |
| 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Freiburg : Germany (2009) |
|
|
|
|
| An Order on Sets of Tilings Corresponding to an Order on Languages |
|
|
| Nathalie Aubrun 1Mathieu Sablik 2 |
|
|
| (2009) |
|
|
|
| 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. |
|
|
|
|
|
|
|
|
|
|
|
| 1: | Laboratoire d'Informatique Gaspard-Monge (LIGM) |
|
|
|
Université Paris-Est Marne-la-Vallée (UPEMLV) – ESIEE – Ecole des Ponts ParisTech – Fédération de Recherche Bézout – CNRS : UMR8049 |
|
|
| 2: | Laboratoire d'Analyse, Topologie, Probabilités (LATP) |
|
|
|
CNRS : UMR6632 – Université de Provence - Aix-Marseille I – Université Paul Cézanne - Aix-Marseille III |
|
|
|
|
|
|
|
|
|
| Domain | : | Computer Science/Discrete Mathematics |
|
|
| tiling – subshift – Turing machine with oracle – subdynamics |
|
|
|
| Attached file list to this document: | ||||||||||
|
||||||||||
|
|
|
| inria-00359625, version 1 | |
| http://hal.inria.fr/inria-00359625 | |
| oai:hal.inria.fr:inria-00359625 | |
| From: Publications Loria | |
| Submitted on: Monday, 9 February 2009 08:38:33 | |
| Updated on: Wednesday, 11 February 2009 17:22:55 | |
