Article (Scientific journals)
The growth function of S-recognizable sets
Charlier, Emilie; Rampersad, Narad
2011In Theoretical Computer Science, 412 (39), p. 5400-5408
Peer Reviewed verified by ORBi
 

Files


Full Text
TCS8413.pdf
Author postprint (457.73 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
S-recognizable set; Growth function; Finite automaton; Regular language; Morphic sequence
Abstract :
[en] A set X ⊆ N is S-recognizable for an abstract numeration system S, if the set rep_S (X) of its representations is accepted by a finite automaton. We show that the growth function of an S-recognizable set is always either Θ((log(n))^(c−df) n^f ) where c, d ∈ N and f ≥ 1, or Θ(n^r θ^(Θ(n^q))), where r, q ∈ Q with q ≤ 1. If the number of words of length n in the numeration language is bounded by a polynomial, then the growth function of an S-recognizable set is Θ(nr ), where r ∈ Q with r ≥ 1. Furthermore, for every r ∈ Q with r ≥ 1, we can provide an abstract numeration system S built on a polynomial language and an S-recognizable set such that the growth function of X is Θ(n^r ). For all positive integers k and ℓ, we can also provide an abstract numeration system S built on an exponential language and an S-recognizable set such that the growth function of X is Θ((log(n))^k n^ℓ).
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie  ;  University of Waterloo > David R. Cheriton School of Computer Science > Mathématiques discrètes
Rampersad, Narad;  Université de Liège - ULiège > Mathématique > Mathématiques Discrètes
Language :
English
Title :
The growth function of S-recognizable sets
Publication date :
2011
Journal title :
Theoretical Computer Science
ISSN :
0304-3975
Publisher :
Elsevier Science, Amsterdam, Netherlands
Volume :
412
Issue :
39
Pages :
5400-5408
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 07 June 2012

Statistics


Number of views
57 (7 by ULiège)
Number of downloads
1 (1 by ULiège)

Scopus citations®
 
4
Scopus citations®
without self-citations
1
OpenCitations
 
2

Bibliography


Similar publications



Contact ORBi