Squares in Partial words

Partial words, or sequences over a finite alphabet that may contain a number of "do not know" symbols or "holes", appear in natural ways in several areas of current interest such as molecular biology, data communication, DNA computing, etc. In these papers, we study the combinatorial problems of square-freeness and overlap-freeness in the context of partial words, generalizing well-known results on full words. In addition, we investigate the problem of counting the number of distinct squares in partial words with an arbitrary number of holes.

Keywords: Combinatorics on words; Partial words; Freeness; Square; Overlap.

Valid XHTML 1.0 Strict Valid CSS!