The upper density of an automatic set is rational

DOI10.5802/JTNB.1135MaRDI QIDQ2211032zbMATH OpenOpenAlexFDO

Authors Jason P. Bell

Publication date 10 November 2020

Published in Journal de Théorie des Nombres de Bordeaux (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

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

zbMATH Keywords

formal languagesCobham's theoremupper densityautomatic set

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata sequences (11B85)

Abstract: Given a natural number $kge2$ and a $k$-automatic set $S$ of natural numbers, we show that the lower density and upper density of $S$ are recursively computable rational numbers and we provide an algorithm for computing these quantities. In addition, we show that for every natural number $kge2$ and every pair of rational numbers $$ with $$ or with $$ there is a $k$-automatic subset of the natural numbers whose lower density and upper density are $alpha$ and $$ respectively, and we show that these are precisely the values that can occur as the lower and upper densities of an automatic set.

Recommendations

• Automatic sets of rational numbers
• \(k\)-automatic sets of rational numbers
• The asymptotic distribution of elements in automatic sequences
• (Logarithmic) densities for automatic sequences along primes and squares
• When is an automatic set an additive basis?

Cites work

• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3065861 (Why is no real title available?)
• A note on the density of inherently ambiguous context-free languages
• Automatic Sequences
• Computer programming and formal systems
• Factoring polynomials with rational coefficients
• Logarithmic frequency in morphic sequences
• On \(p\)th roots of stochastic matrices
• Uniform tag sequences

Cited in

(7)

• Automatic sets of rational numbers
• How to prove that a sequence is not automatic
• The asymptotic distribution of elements in automatic sequences
• (Logarithmic) densities for automatic sequences along primes and squares
• Squarefree words with interior disposable factors
• Quantitative estimates for the size of an intersection of sparse automatic sets
• \(k\)-automatic sets of rational numbers

This page was built for publication: The upper density of an automatic set is rational

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