7 problems

Let $\Sigma=\{0,1\}$, let $\mathcal L_{\mathrm{PN1}}$ be the language of prefix normal words, and call a prefix normal word $w$ extension-critical if $w1$ is not prefix normal. Let…

Let $\Sigma=\{0,1\}$, let $\mathcal L_{\mathrm{PN1}}$ be the language of prefix normal words, and let $\textit{ecrit}(n)$ count the extension-critical words in…

Let $v,w\in 1\{0,1\}^*$ be distinct prefix normal binary words. For each $m\geq 1$, let $\textit{ext}(v,m)$ and $\textit{ext}(w,m)$ denote the numbers of length-$m$ extensions that…

Let $w$ be a binary word, and let ${\sc MemberPN}(w)$ be the proposed membership tester that applies the two linear-time rejection tests followed by a quadratic-time prefix-normali…

Let $M$ be the set of binary strings not rejected by the first, linear-time phase of the proposed two-phase membership tester for prefix normal words. The first phase is assumed to…

For each $n$, let $\textit{pnw}(n)$ be the number of prefix normal binary words of length $n$, and let $\textit{crit}(n)$ be the number of extension-critical words of length $n$. P…

Let $v,w e 0$ be distinct prefix normal binary words, with extension counts $textit{ext}(v,m)$ and $textit{ext}(w,m)$ denoting the numbers of prefix normal extensions of length $m$…