Extension-language separation conjecture for prefix normal words

Let v,w1{0,1}v,w\in 1\{0,1\}^* be distinct prefix normal binary words. For each m1m\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 vwv\neq w, then the infinite sequences

(ext(v,m))m1and(ext(w,m))m1(\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.

Sources & referencesView supporting material

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.