Multi angle

H 1 Logic, decidability and numeration systems - Lecture 1

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

    Loading the player...

    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 nombres
    Organisateurs de la rencontre : 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.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


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

Ressources Electroniques

Books & Print journals

Recherche avancée