The growth function of S-recognizable sets

DOI10.1016/J.TCS.2011.05.057zbMATH Open1222.68100arXiv1101.0036OpenAlexW2962987831MaRDI QIDQ719280FDOQ719280

Authors: Émilie Charlier, Narad Rampersad

Publication date: 10 October 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A set

X s u b s e t e q m a t h b b N

is S-recognizable for an abstract numeration system S if the set

e p_{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

T h e t a ((l o g (n))^{c - d f} n^{f})

where

c, d i n m a t h b b N

and

f g e 1

, or

T h e t a (n^{r} h e t a^{T h e t a (n^{q})})

, where

r, q i n m a t h b b Q

with

q l e 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

T h e t a (n^{r})

, where

r i n m a t h b b Q

with

r g e 1

. Furthermore, for every

r i n m a t h b b Q

with

r g e 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

T h e t a (n^{r})

. For all positive integers k and l, we can also provide an abstract numeration system S built on a exponential language and an S-recognizable set such that the growth function of X is

T h e t a ((l o g (n))^{k} n^{l})

.

Full work available at URL: https://arxiv.org/abs/1101.0036

Recommendations

zbMATH Keywords

regular language growth function finite automaton \(S\)-recognizable set morphic sequence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Cites Work

Cited In (4)

Uses Software

OEIS

This page was built for publication: The growth function of \(S\)-recognizable sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q719280)