PROPERTIES OF PSEUDO-PRIMITIVE WORDS AND THEIR APPLICATIONS
Lila Kari, Benoît Masson, Shinnosuke Seki · International Journal of Foundations of Computer Science · 2011
A pseudo-primitive word with respect to an antimorphic involution θ is a word which cannot be written as a catenation of occurrences of a strictly shorter word t and θ(t). Properties of pseudo-primitive words are investigated in this paper. These properties link pseudo-primitive words with essential notions in combinatorics on words such as primitive words, (pseudo)-palindromes, and (pseudo)-commutativity. Their applications include an improved solution to the extended Lyndon-Schützenberger equation u1u2 ⋯ uℓ = v1 ⋯ vnw1 ⋯ wm, where u1, … , uℓ ∈ {u,θ(u)}, v1, …, vn ∈ {v, θ(v)}, and w1, … , wm ∈ {w, θ(w)} for some words u, v, w, integers ℓ, n, m ≥ 2, and an antimorphic involution θ. We prove that for ℓ ≥ 4, n, m ≥ 3, this equation implies that u, v, w can be expressed in terms of a common word t and its image θ(t). Moreover, several cases of this equation where ℓ = 3 are examined.