Decidability Problems for Self-induced Systems Generated by a Substitution

Timo Jolivet 1 Anne Siegel 2, *
* Auteur correspondant
2 Dyliss - Dynamics, Logics and Inference for biological Systems and Sequences
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : In this talk we will survey several decidability and undecidability results on topological properties of self-affine or self-similar fractal tiles. Such tiles are obtained as fixed point of set equations governed by a graph. The study of their topological properties is known to be complex in general: we will illustrate this by undecidability results on tiles generated by multitape automata. In contrast, the class of self affine tiles called Rauzy fractals is particularly interesting. Such fractals provide geometrical representations of self-induced mathematical processes. They are associated to one-dimensional combinatorial substitutions (or iterated morphisms). They are somehow ubiquitous as self-replication processes appear naturally in several fields of mathematics. We will survey the main decidable topological properties of these specific Rauzy fractals and detail how the arithmetic properties yields by the combinatorial substitution underlying the fractal construction make these properties decidable. We will end up this talk by discussing new questions arising in relation with continued fraction algorithm and fractal tiles generated by S-adic expansion systems.
Type de document :
Communication dans un congrès
MCU 2015 : Machines, Computation and Universality, 2015, Famagusta, Cyprus. Springer, Lecture Notes in Computer Science 9288, 2015, MCU: Machines, Computation and Universality (7th conference). 〈http://mcu2015.emu.edu.tr/mcu2015/〉. 〈10.1007/978-3-319-23111-2〉
Liste complète des métadonnées

Littérature citée [74 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01196152
Contributeur : Anne Siegel <>
Soumis le : samedi 12 septembre 2015 - 11:58:29
Dernière modification le : mercredi 11 avril 2018 - 02:01:19
Document(s) archivé(s) le : lundi 28 décembre 2015 - 23:02:45

Fichiers

report.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Timo Jolivet, Anne Siegel. Decidability Problems for Self-induced Systems Generated by a Substitution. MCU 2015 : Machines, Computation and Universality, 2015, Famagusta, Cyprus. Springer, Lecture Notes in Computer Science 9288, 2015, MCU: Machines, Computation and Universality (7th conference). 〈http://mcu2015.emu.edu.tr/mcu2015/〉. 〈10.1007/978-3-319-23111-2〉. 〈hal-01196152〉

Partager

Métriques

Consultations de la notice

276

Téléchargements de fichiers

156