Abstract

A word is a sequence of letters over an alphabet, and a partial word is a sequence of letters in which some positions are undefined. Undefined positions are referred to as holes and are represented by the symbol . A hole is compatible with every letter. In this paper, we study occurrences of abelian borders, which are prefixes and suffixes that are permutations of each other (for partial words, prefixes and suffixes that are compatible with permutations of each other). In particular, we generalize results about full words to partial words and develop techniques for identifying and counting abelian borders.

Keywords: Combinatorics on Words; Partial Words; Abelian Borders