m
F x |
L
     
Multi angle

H 1 On centauric subshifts

Auteurs : Romashchenko, Andrei (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...
    Résumé : We discuss subshifts of finite type (tilings) that combine virtually opposite properties, being at once very simple and very complex. On the one hand, the combinatorial structure of these subshifts is rather simple: we require that all their configurations are quasiperiodic, or even that all configurations contain exactly the same finite patterns (in the last case a subshift is transitive, i.e., irreducible as a dynamical system). On the other hand, these subshifts are complex in the sense of computability theory: all their configurations are non periodic or even non-computable, or all their finite patterns have high Kolmogorov complexity, the Turing degree spectrum is rather sophisticated, etc.
    We start with the simplest example of such centaurisme with an SFT that is minimal and contains only aperiodic (and quasiperiodic) configurations. Then we discuss how far these heterogeneous properties can be strengthened without getting mutually exclusive.
    This is a joint work with Bruno Durand (Univ. de Montpellier).

    Codes MSC :
    03B80 - Other applications of logic
     68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 06/07/2016
      Date de captation : 22/06/2016
      Collection : Research talks ; Computer Science ; Logic and Foundations
      Format : MP4
      Durée : 01:05:07
      Domaine : Computer Science ; Logic and Foundations
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2016-06-22_Romashchenko.mp4
    Informations sur la rencontre

    Nom de la rencontre : Computability, randomness and applications / Calculabilité, hasard et leurs applications
    Organisateurs de la rencontre : Bienvenu, Laurent ; Jeandel, Emmanuel ; Porter, Christopher
    Dates : 20/06/2016 - 24/06/2016
    Année de la rencontre : 2016
    URL Congrès : http://conferences.cirm-math.fr/1408.html

    Citation Data

    DOI : 10.24350/CIRM.V.19006203
    Cite this video as: Romashchenko, Andrei (2016). On centauric subshifts. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19006203
    URI : http://dx.doi.org/10.24350/CIRM.V.19006203

    Voir aussi

    Bibliographie

    1. [1] Ballier, A. (2009). Propriétés structurelles, combinatoires et logiques des pavages. Thèse de doctorat. Marseille : Université d'Aix-Marseille, 2009, 137 p. - http://pageperso.lif.univ-mrs.fr/~alexis.ballier/these/these.pdf

    2. [2] Ballier, A., & Jeandel, E. (2010). Computing (or not) quasi-periodicity functions of tilings. In J. Kari (Ed.), Proceedings of JAC 2010 (pp. 54–64). Turku: Turku Center for Computer Science - https://www.doria.fi/bitstream/handle/10024/66298/LN13.digi.pdf

    3. [3] Jeandel, E., & Vanier, P. (2013). Turing degrees of multidimensional SFTs. Theoretical Computer Science, 505 (2013), 81–92 - http://dx.doi.org/10.1016/j.tcs.2012.08.027

    4. [4] Hochman, M., & Vanier, P. (2014). Turing degree spectra of minimal subshifts. - http://arxiv.org/abs/1408.6487

    5. [5] Durand, B., & Romashchenko, A. (2015). Quasiperiodicity and non-computability in tilings. In G.F. Italiano, G. Pighizzini, & D.T. Sannella (Eds.), Mathematical foundations of computer science 2015, Part 1 (pp. 218–230). Berlin: Springer - http://www.springer.com/gb/book/9783662480564

Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée

0
Z