• D

F Nous contacter

0

# Multi angle

O

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

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

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 nombresOrganisteurs Congrès : Berthé, Valérie ; Rigo, MichelDates : 28/11/16 - 02/12/16 Année de la rencontre : 2016 URL Congrès : http://conferences.cirm-math.fr/1502.htmlCitation DataDOI : 10.24350/CIRM.V.19098203Cite this video as: Aubrun, Nathalie (2016). About the domino problem on finitely generated groups - Lecture 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19098203URI : http://dx.doi.org/10.24350/CIRM.V.19098203

### Voir aussi

Bibliographie

Z