Insertions Yielding Equivalent Double Occurrence Words

• Published in: Fundamenta informaticae 2019, Vol.171 (1-4), p.113-132
• Main Authors: Cruz, Daniel A., Ferrari, Margherita Maria, Jonoska, Nataša, Nabergall, Lukas, Saito, Masahico
• Format: Article
• Language: English
• Subjects: Equivalence
• ISSN: 0169-2968; 1875-8681
• DOI: 10.3233/FI-2020-1875

A double occurrence word (DOW) is a word in which every symbol appears exactly twice; two DOWs are equivalent if one is a symbol-to-symbol image of the other. We consider the so called repeat pattern (αα) and the return pattern (αα R ), with gaps allowed between the α’s. These patterns generalize square and palindromic factors of DOWs, respectively. We introduce a notion of inserting repeat/return words into DOWs and study how two distinct insertions into the same word can produce equivalent DOWs. Given a DOW w, we characterize the structure of w which allows two distinct insertions to yield equivalent DOWs. This characterization depends on the locations of the insertions and on the length of the inserted repeat/return words and implies that when one inserted word is a repeat word and the other is a return word, then both words must be trivial (i.e., have only one symbol). The characterization also introduces a method to generate families of words recursively.