Extension-language separation conjecture for prefix normal words

About 10 years old · traced to

Let v,w∈1{0,1}∗v,w\in 1\{0,1\}^* be distinct prefix normal binary words. For each m≥1m\geq 1, let ext(v,m)\textit{ext}(v,m) and ext(w,m)\textit{ext}(w,m) denote the numbers of length-mm extensions that produce prefix normal words. Extension-language separation 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 separation of the extension languages themselves; whether their growth, or equivalently these counting sequences, always differs was left unresolved.

References

Primary source

Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Frank Ruskey and Joe Sawada, “On Prefix Normal Words and Prefix Normal Forms”, arXiv:1611.09017 (2016).

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.