m
• E

F Nous contacter

0

Multi angle

H 1 Logic, decidability and numeration systems - Lecture 1

Auteurs : Charlier, Émilie (Auteur de la Conférence)
CIRM (Editeur )

Résumé : The theorem of Büchi-Bruyère states that a subset of $N^d$ is $b$-recognizable if and only if it is $b$-definable. As a corollary, the first-order theory of $(N,+,V_b)$ is decidable (where $V_b(n)$ is the largest power of the base $b$ dividing $n$). This classical result is a powerful tool in order to show that many properties of $b$-automatic sequences are decidable. The first part of my lecture will be devoted to presenting this result and its applications to $b$-automatic sequences. Then I will move to $b$-regular sequences, which can be viewed as a generalization of $b$-automatic sequences to integer-valued sequences. I will explain bow first-order logic can be used to show that many enumeration problems of $b$-automatic sequences give rise to corresponding $b$-regular sequences. Finally, I will consider more general frameworks than integer bases and (try to) give a state of the art of the research in this domain.

Codes MSC :
03B25 - Decidability of theories and sets of sentences
11B85 - Automata sequences
68Q45 - Formal languages and automata
68R15 - Combinatorics on words

 Informations sur la Vidéo Langue : Anglais Date de publication : 08/12/16 Date de captation : 30/11/16 Collection : Research School ; Computer Science ; Logic and Foundations ; Number Theory Format : MP4 Durée : 01:07:31 Domaine : Computer Science ; Number Theory ; Logic and Foundations Audience : Chercheurs ; Doctorants , Post - Doctorants Download : https://videos.cirm-math.fr/2016-11-30_Charlier.mp4 Informations sur la rencontre Nom de la rencontre : Combinatorics, automata and number theory / Combinatoire, automates et théorie des nombresOrganisateurs de la rencontre : 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 Data DOI : 10.24350/CIRM.V.19098403 Cite this video as: Charlier, Émilie (2016). Logic, decidability and numeration systems - Lecture 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19098403 URI : http://dx.doi.org/10.24350/CIRM.V.19098403

Voir aussi

Bibliographie

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

Ressources Electroniques

Books & Print journals

Recherche avancée

0
Z