Reference : Logic, Decidability and Numeration Systems
Scientific congresses and symposiums : Unpublished conference/Abstract
Physical, chemical, mathematical & earth Sciences : Mathematics
Logic, Decidability and Numeration Systems
Charlier, Emilie mailto [Université de Liège > Département de mathématique > Mathématiques discrètes >]
Combinatorics, Automata and Number Theory (CANT)
from 28-11-2016 to 02-12-2016
[en] Numeration systems ; Logic ; Recognizable sets
[en] 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 how 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.
This is a 3-hour mini-course. Part of it was on the blackboard (no slides). The first hour was videotaped :

File(s) associated to this reference

Fulltext file(s):

Open access
CANT2016-talk.pdfAuthor postprint607.02 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.