Article (Scientific journals)
Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure
Lacroix, Anne; Rampersad, Narad; Rigo, Michel et al.
2012In Fundamenta Informaticae, 116, p. 175-187
Peer Reviewed verified by ORBi
 

Files


Full Text
final.pdf
Author preprint (148.19 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
integer base; syntactic monoid; complexity; ultimately periodic set; decision problem
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 a well studied problem: decide whether or not a b-recognizable set of integers is ultimately periodic.
Disciplines :
Computer science
Mathematics
Author, co-author :
Lacroix, Anne ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Rampersad, Narad
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 and application to a decision procedure
Publication date :
2012
Journal title :
Fundamenta Informaticae
ISSN :
0169-2968
Publisher :
IOS Press
Volume :
116
Pages :
175-187
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 16 July 2012

Statistics


Number of views
178 (30 by ULiège)
Number of downloads
224 (16 by ULiège)

Scopus citations®
 
5
Scopus citations®
without self-citations
2
OpenCitations
 
3

Bibliography


Similar publications



Contact ORBi