The asymptotic number of prefix normal words

DOI10.1016/J.TCS.2019.03.036zbMATH Open1423.68365arXiv1903.07957OpenAlexW2921927228MaRDI QIDQ2317872FDOQ2317872

Authors: Stefanie Gerke, Paul Balister 

Publication date: 13 August 2019

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

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)}$.

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

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

zbMATH Keywords

random constructionprefix normal words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• On combinatorial generation of prefix normal words
• On prefix normal words
• On prefix normal words and prefix normal forms
• Leaf realization problem, caterpillar graphs and prefix normal words

Cited In (6)

• Weighted prefix normal words: mind the gap
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• Title not available (Why is that?)
• 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

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)