Bordered and Primitive Partial Words

Abstract

We consider the problems of counting the maximum number of holes that a partial word can contain, provided that it satisfies one of the following:

· The word is primitive

· The word is unbordered

· The word has a longest border of length l

For primitive words, an explicit formula is given. For unbordered words and words with longest border l we prove some recurrence relations which help bound these numbers. We also investigate the relationship between border arrays and explore how to count the number of p-canonical partial words which satisfy a given border array.

Keywords: Combinatorics on words; Bordered partial words; Primitive partial words; Border arrays.