Reference : Syntactic complexity of ultimately periodic sets of integers and application to a dec...
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/127570
Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure
English
Lacroix, Anne mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Rampersad, Narad [ > > ]
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Vandomme, Elise mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
2012
Fundamenta Informaticae
IOS Press
116
175-187
Yes (verified by ORBi)
International
0169-2968
[en] integer base ; syntactic monoid ; complexity ; ultimately periodic set ; decision problem
[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 a well studied problem: decide whether or not a b-recognizable set of integers is ultimately periodic.
Researchers
http://hdl.handle.net/2268/127570
10.3233/FI-2012-677

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
final.pdfAuthor preprint144.72 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.