Insertions Yielding Equivalent Double Occurrence Words

Issue title: Interdisciplinary Nature of Information Processing Special Issue Dedicated to Giancarlo Mauri on the Occasion of His 70th Birthday

Guest editors: Alberto Dennunzio, Gheorghe Păun, Grzegorz Rozenberg and Claudio Zandron

Article type: Research Article

Authors: Cruz, Daniel A.^{a; *} | Ferrari, Margherita Maria^a | Jonoska, Nataša^a | Nabergall, Lukas^b | Saito, Masahico^c

Affiliations: [a] University of South Florida, Tampa FL, 33620, USA. [email protected], [email protected], [email protected] | [b] University of Waterloo, Waterloo ON, N2L 3G1, Canada. [email protected] | [c] University of South Florida, Tampa FL, 33620, USA. [email protected]

Correspondence: [*] Address for correspondence: University of South Florida, Tampa FL, 33620, USA

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 (αα) 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.

DOI: 10.3233/FI-2020-1875

Journal: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 113-132, 2020