2010/02/22 by Lila Kari, Benoît Masson, Kari, Lila +3 · 1 citation
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #semigroups and automata theory
paper · doi:10.48550/arxiv.1002.4084
openalex publication_date 2010/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 u1 u2 ... ul = v1 ... vn w1 ... wm, where u1, ..., ul ∈ u, θ(u), v1, ..., vn ∈ v, θ(v), and w1, ..., wm ∈ w, \theata(w) for some words u, v, w, integers l, n, m ≥ 2, and an antimorphic involution θ. We prove that for l ≥ 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 l = 3 are examined.