The asymptotic number of prefix normal words

DOI10.1016/J.TCS.2019.03.036MaRDI QIDQ2317872zbMATH OpenOpenAlexFDO

Authors Stefanie Gerke, Paul Balister

Publication date 13 August 2019

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

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

zbMATH Keywords

random constructionprefix normal words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We show that the number of prefix normal binary words of length $n$ is $2^{n-Theta((logn{)}^2)}$. We also show that the maximum number of binary words of length $n$ with a given fixed prefix normal form is $2^{n-O(sqrtnlogn)}$.

Recommendations

• On prefix normal words and prefix normal forms
• On infinite prefix normal words
• On infinite prefix normal words
• On combinatorial generation of prefix normal words
• Weighted prefix normal words: mind the gap

Cites work

• scientific article; zbMATH DE number 52032 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Leaf realization problem, caterpillar graphs and prefix normal words
• On combinatorial generation of prefix normal words
• On prefix normal words
• On prefix normal words and prefix normal forms
• Probability Inequalities for Sums of Bounded Random Variables

Cited in

(6)

• Weighted prefix normal words: mind the gap
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• scientific article; zbMATH DE number 3910298 (Why is no real title available?)
• On prefix normal words and prefix normal forms
• On infinite prefix normal words
• On the asymptotics of the number of binary words with a given length of a maximal series

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The asymptotic number of prefix normal words

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