Symbol Separation in Double Occurrence Words

A double occurrence word (DOW) is a word in which every symbol appears exactly twice. We define the symbol separation of a DOW w to be the number of letters between the two copies of a symbol, and the separation of w to be the sum of separations over all symbols in w . We then analyze relationship a...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2020-11, Vol.31 (7), p.915-928
Main Authors: Jonoska, Nataša, Saito, Masahico, Kim, Hwee, Mostowski, Brad
Format: Article
Language:English
Subjects:
Separation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A double occurrence word (DOW) is a word in which every symbol appears exactly twice. We define the symbol separation of a DOW w to be the number of letters between the two copies of a symbol, and the separation of w to be the sum of separations over all symbols in w . We then analyze relationship among size, reducibility and separation of DOWs. Specifically, we provide tight bounds of separations of DOWs with a given size and characterize the words that attain those bounds. We show that all separation numbers within the bounds can be realized. We present recursive formulas for counting the numbers of DOWs with a given separation under various restrictions, such as the number of irreducible factors. These formulas can be obtained by inductive construction of all DOWs with the given separation.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054120500343