Syntactic complexity of ultimately periodic sets of integers

Reference : Syntactic complexity of ultimately periodic sets of integers


	Document type :	Scientific congresses and symposiums : Paper published in a journal
	Discipline(s) :	Engineering, computing & technology : Computer science Physical, chemical, mathematical & earth Sciences : Mathematics
	To cite this reference:	http://hdl.handle.net/2268/85075

Title :	Syntactic complexity of ultimately periodic sets of integers
Language :	English
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 >]
Publication date :	2011
Journal title :	Lecture Notes in Computer Science
Publisher :	Springer
Volume :	6638
Pages :	477-488
Peer reviewed :	Yes
On invitation :	No
Audience :	International
ISSN :	0302-9743
e-ISSN :	1611-3349
City :	Berlin
Country :	Germany
Event name :	LATA 2011 (5th conf. Languages and Automata, Theory and Applications)
Event date :	from 26-05-2011 to 30-05-2011
Event place (city) :	Tarragona
Event country :	Spain
Keywords :	[en] syntactic monoid ; complexity ; regular language ; numeration system ; 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 some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic.
Permalink :	http://hdl.handle.net/2268/85075
DOI :	10.1007/978-3-642-21254-3_38

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Restricted access	rigo-vandomme2.pdf		Author preprint	179.62 kB	Request copy

All documents in ORBi are protected by a user license.