The asymptotic number of prefix normal words

Abstract: We show that the number of prefix normal binary words of length

n

is

2^{n - T h e t a ((l o g n)^{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 (s q r t n l o g n)}

.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

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