Insertions yielding equivalent double occurrence words

DOI10.3233/FI-2020-1875zbMATH Open1435.68250arXiv1811.11739OpenAlexW2989980706MaRDI QIDQ5114211FDOQ5114211

Daniel Cruz, Masahico Saito, Margherita Maria Ferrari, Nataşa Jonoska, Lukas Nabergall

Publication date: 21 June 2020

Published in: Fundamenta Informaticae (Search for Journal in Brave)

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 ($alphaalpha$) and the return pattern ($alphaalph{a}^R$), with gaps allowed between the $alpha$'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.

Full work available at URL: https://arxiv.org/abs/1811.11739

Recommendations

• Symbol Separation in Double Occurrence Words
• Patterns and distances in words related to DNA rearrangement
• Counting irreducible double occurrence words
• scientific article; zbMATH DE number 554160
• Double occurrence words: their graphs and matrices

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cited In (6)

• Combinatorial methods for barcode analysis
• Title not available (Why is that?)
• Transformations of assembly number for 4-regular graphs
• Double occurrence words: their graphs and matrices
• Reductions on Double Occurrence Words
• Symbol Separation in Double Occurrence Words

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)