Distinct prefix normal words have distinct extension-count sequences

About 12 years old · traced to

Let v,we0v,w e 0 be distinct prefix normal binary words, with extension counts ext(v,m)\textit{ext}(v,m) and ext(w,m)\textit{ext}(w,m) denoting the numbers of prefix normal extensions of length mm. Distinct-extension-sequence conjecture. If v≠wv\neq w, then the infinite sequences

(ext(v,m))m≥1and(ext(w,m))m≥1(\textit{ext}(v,m))_{m\geq 1}\quad\text{and}\quad(\textit{ext}(w,m))_{m\geq 1}

are different. The preceding lemma establishes the analogous claim for the extension languages themselves, but the paper does not prove that their growth sequences differ.

References

Primary source

Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Frank Ruskey and Joe Sawada, “Normal, Abby Normal, Prefix Normal”, arXiv:1404.2824 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.