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

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,vext(Lk,α)u,v\in {\sf ext}(L_{k,\alpha}) can be joined by a word ww such that uwvext(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.

Sources & referencesView supporting material

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.