Paper published in a book (Scientific congresses and symposiums)
State complexity of the multiples of the Thue-Morse set
Charlier, Emilie; Cisternino, Célia; Massuir, Adeline
2019In Actes de Numeration 2019
Peer reviewed
 

Files


Full Text
Numeration2019_paper_7.pdf
Author postprint (258.21 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Evil numbers; State complexity; Numeration systems
Abstract :
[en] The Thue-Morse set is the set of those nonnegative integers whose binary expansions have an even number of 1. Its characteristic sequence is given by the famous Thue-Morse word, which is the fixed point starting with 1 of the morphism 0->01,1->10. We obtain an exact formula for the state complexity of the multiplication by a constant of the Thue-Morse set T with respect to any base b which is a power of 2. Our proof is constructive and we are able to explicitly provide the minimal automaton of the language of all 2^p-expansions of the set of integers mT for any positive integers m and p.
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Cisternino, Célia ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Massuir, Adeline ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
State complexity of the multiples of the Thue-Morse set
Publication date :
2019
Event name :
Numeration 2019
Event place :
Vienne, Austria
Event date :
du 8 juillet 2019 au 12 juillet 2019
Audience :
International
Main work title :
Actes de Numeration 2019
Publisher :
Erwin Schrödinger Institute, Vienne, Austria
Peer reviewed :
Peer reviewed
Available on ORBi :
since 15 May 2024

Statistics


Number of views
10 (0 by ULiège)
Number of downloads
4 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi