Bordered and Primitive Partial Words

F. Blanchet-Sadri    Michelle Bodnar   Joe Hidakatsu

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.