Insertions yielding equivalent double occurrence words

Abstract: 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 (

a l p h a a l p h a

) and the return pattern (

a l p h a a l p h a^{R}

), with gaps allowed between the

a l p h a

'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.

Recommendations

Cited in

(8)

This page was built for publication: Insertions yielding equivalent double occurrence words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5114211)