Reference : The growth function of S-recognizable sets
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/124660
The growth function of S-recognizable sets
English
Charlier, Emilie mailto [University of Waterloo > David R. Cheriton School of Computer Science > Mathématiques discrètes > >]
Rampersad, Narad [Université de Liège - ULg > Mathématique > Mathématiques Discrètes > >]
2011
Theoretical Computer Science
Elsevier Science
412
39
5400-5408
Yes (verified by ORBi)
International
0304-3975
Amsterdam
The Netherlands
[en] S-recognizable set ; Growth function ; Finite automaton ; Regular language ; Morphic sequence
[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^ℓ).
Researchers ; Professionals
http://hdl.handle.net/2268/124660

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
TCS8413.pdfAuthor postprint447 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.