No full text
Unpublished conference/Abstract (Scientific congresses and symposiums)
Is Büchi's theorem useful for you?
Rigo, Michel
2015Automatic sequences...
 

Files


Full Text
No document available.
Annexes
Rigo.pdf
Publisher postprint (555.41 kB)
presentation
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
decidability; automatic sequence; combinatorics on words
Abstract :
[en] Almost a century ago, Presburger showed that the first order theory of the natural numbers with addition is decidable. Following the work of Büchi in 1960, this result still holds when adding a function $V_k$ to the structure, where $V_k(n)$ is the largest power of $k\ge 2$ diving $n$. In particular, this leads to a logical characterization of the $k$-automatic sequences. During the last few years, many applications of this result have been considered in combinatorics on words, mostly by J. Shallit and his coauthors. In this talk, we will present this theorem of Büchi where decidability relies on finite automata.Then we will review some results about automatic sequences or morphic words that can be proved automatically (i.e., the proof is carried on by an algorithm). Finally, we will sketch the limitation of this technique. With a single line formula, one can prove automatically that the Thue-Morse word has no overlap but, hopefully, not all the combinatorial properties of morphic words can be derived in this way.
Disciplines :
Mathematics
Author, co-author :
Rigo, Michel  ;  Université de Liège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Is Büchi's theorem useful for you?
Publication date :
28 May 2015
Event name :
Automatic sequences...
Event date :
from 25-5-2015 to 29-5-2015
By request :
Yes
Audience :
International
Available on ORBi :
since 28 May 2015

Statistics


Number of views
69 (5 by ULiège)
Number of downloads
33 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi