Automata; State complexity; Thue-Morse; Regular Language
Abstract :
[en] In this talk, I present the constructive proof of the theorem which states that the state complexity of the set mT in base 2^p is equal to 2k+ ceil{z/p} where T is the thue morse set and m=k2^z with k odd. This research is a joint work with Emilie Charlier and Adeline Massiur.
Disciplines :
Mathematics
Author, co-author :
Cisternino, Célia ; 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 :
08 July 2019
Event name :
Numeration 2019: Numeration and Subsitutions
Event organizer :
Erwin Schrödinger Institut
Event place :
Vienna, Austria
Event date :
08/07/2019 -> 12/07/19
Audience :
International
Funders :
Fédération Wallonie Bruxelles. Fonds de la Recherche Scientifique - F.R.S.-FNRS