The growth function of S-recognizable sets

DOI10.1016/J.TCS.2011.05.057MaRDI QIDQ719280zbMATH OpenOpenAlexFDO

Authors Émilie Charlier, Narad Rampersad

Publication date 10 October 2011

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

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

zbMATH Keywords

regular languagegrowth functionfinite automaton\(S\)-recognizable setmorphic sequence

Mathematics Subject Classification ID

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

Abstract: A set $XsubseteqmathbbN$ 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 $Theta((log(n){)}^{c-df}{n}^f)$ where $c,dinmathbbN$ and $fge1$, or $Theta(n^{r}het{a}^{Theta(n^q)})$, where $r,qinmathbbQ$ with $qle1$. 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 $Theta(n^r)$, where $rinmathbbQ$ with $rge1$. Furthermore, for every $rinmathbbQ$ with $rge1$, 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 $Theta(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 $Theta((log(n){)}^k{n}^l)$.

Recommendations

• Multi-dimensional sets recognizable in all abstract numeration systems
• scientific article; zbMATH DE number 1929973
• Construction of regular languages and recognizability of polynomials
• Abstract numeration systems on bounded languages and multiplication by a constant
• Numeration systems on a regular language: Arithmetic operations, recognizability and formal power series

Cites work

• scientific article; zbMATH DE number 4195200 (Why is no real title available?)
• scientific article; zbMATH DE number 5707089 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 1916667 (Why is no real title available?)
• Abstract numeration systems on bounded languages and multiplication by a constant
• Automatic Sequences
• Characterizing regular languages with polynomial densities
• Construction of regular languages and recognizability of polynomials
• Generalization of automatic sequences for numeration systems on a regular language
• Multi-dimensional sets recognizable in all abstract numeration systems
• Multidimensional generalized automatic sequences and shape-symmetric morphic words
• Numeration systems on a regular language
• Syndeticity and independent substitutions
• The On-Line Encyclopedia of Integer Sequences

Cited in

(4)

• scientific article; zbMATH DE number 7453075 (Why is no real title available?)
• Asymptotic properties of free monoid morphisms
• First-order logic and numeration systems
• Minimal automaton for multiplying and translating the Thue-Morse set

Describes a project that uses

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)