The growth function of S-recognizable sets
A set X subset of 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 Theta((log(n))(c-df) n(f)) where c,d is an element of N and f >= 1, or Theta(n(r)theta(Theta(nq))), where r, q is an element of Q with q  = 1. Furthermore, for every r is an element of Q with r >= 1, we can provide an abstract numeration systems built on a polynomial language and an S-recognizable set such that the growth function of X is Theta(n(r)). For all positive integers k and l, 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 Theta ((log(n))(k)n(l)). (C) 2011 Elsevier B.V. All rights reserved.
growth function s-recognizable set finite automaton regular language morphic sequence