syntactic monoid; complexity; numeration system; decision problem; regular languages
Abstract :
[en] We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic.
Disciplines :
Mathematics
Author, co-author :
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Vandomme, Elise ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Syntactic complexity of ultimately periodic sets of integers
