F Nous contacter


Multi angle About the domino problem on finitely generated groups - Lecture 1

Auteurs : Aubrun, Nathalie (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : Subshifts of finite type are of high interest from a computational point of view, since they can be described by a finite amount of information - a set of forbidden patterns that defines the subshift - and thus decidability and algorithmic questions can be addressed. Given an SFT $X$, the simplest question one can formulate is the following: does $X$ contain a configuration? This is the so-called domino problem, or emptiness problem: for a given finitely presented group $0$, is there an algorithm that determines if the group $G$ is tilable with a finite set of tiles? In this lecture I will start with a presentation of two different proofs of the undecidability of the domino problem on $Z^2$. Then we will discuss the case of finitely generated groups. Finally, the emptiness problem for general subshifts will be tackled.

    Codes MSC :
    03B25 - Decidability of theories and sets of sentences
    37B50 - Multi-dimensional shifts of finite type, tiling dynamics
    68Q45 - Formal languages and automata

      Informations sur la Vidéo

      Réalisateur : Hennenfent, Guillaume
      Langue : Anglais
      Date de publication : 08/12/16
      Date de captation : 29/11/16
      Collection : Research schools
      Format : MP4
      Durée : 00:59:43
      Domaine : Computer Science ; Dynamical Systems & ODE ; Logic and Foundations
      Audience : Chercheurs ; Etudiants Science Cycle 2 ; Doctorants , Post - Doctorants
      Download : http://videos.cirm-math.fr/2016-11-29_Aubrun.mp4

    Informations sur la rencontre

    Nom du congrès : Combinatorics, automata and number theory / Combinatoire, automates et théorie des nombres
    Organisteurs Congrès : Berthé, Valérie ; Rigo, Michel
    Dates : 28/11/16 - 02/12/16
    Année de la rencontre : 2016
    URL Congrès : http://conferences.cirm-math.fr/1502.html

    Citation Data

    DOI : 10.24350/CIRM.V.19098203
    Cite this video as: Aubrun, Nathalie (2016). About the domino problem on finitely generated groups - Lecture 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19098203
    URI : http://dx.doi.org/10.24350/CIRM.V.19098203

    Voir aussi