Shur's Restivo–Salemi conjecture for power-free languages

About 8 years old · traced to

Let Σk\Sigma_k be a kk-letter alphabet, and let Lk,αL_{k,\alpha} denote the language of α\alpha-power-free finite words over Σk\Sigma_k. For a language LL, write ext(L){\sf ext}(L) for its extendable factors. The language Lk,αL_{k,\alpha} has the Restivo–Salemi property when every pair of words u,v∈ext(Lk,α)u,v\in {\sf ext}(L_{k,\alpha}) can be joined by a word ww such that uwv∈ext(Lk,α)uwv\in {\sf ext}(L_{k,\alpha}). Shur's Restivo–Salemi conjecture. All power-free languages satisfy the Restivo–Salemi property. The property would imply that each power-free language has an infinite recurrent word whose subword complexity has the same growth rate as the language; the source attributes the conjecture to Shur and reports that it is based on extensive numerical studies, but gives no resolution.

References

Primary source

Jeffrey Shallit and Arseny M. Shur, “Subword complexity and power avoidance”, arXiv:1801.05376 (2018).

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.