Reference : Syntactic complexity of ultimately periodic sets of integers
Scientific congresses and symposiums : Paper published in a journal
Engineering, computing & technology : Computer science
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/85075
Syntactic complexity of ultimately periodic sets of integers
English
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 >]
2011
Lecture Notes in Computer Science
Springer
6638
477-488
Yes
No
International
0302-9743
1611-3349
Berlin
Germany
LATA 2011 (5th conf. Languages and Automata, Theory and Applications)
from 26-05-2011 to 30-05-2011
Tarragona
Spain
[en] syntactic monoid ; complexity ; regular language ; numeration system ; 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 some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic.
http://hdl.handle.net/2268/85075

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
rigo-vandomme2.pdfAuthor preprint179.62 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.