# Prefix Arrays, Indeterminate Strings, and Partial Words

## Abstract

We explore prefix arrays of indeterminate strings and partial words. If prefix array $$y$$ is the prefix array for indeterminate string $$w$$, then we say $$w$$ satisfies $$y$$. We use a graph theoretic approach to find a string on a minimum alphabet size which satisfies a given prefix array. We relate the problem of finding a minimum alphabet size to finding edge clique covers of a particular graph, allowing us to bound the minimum alphabet size by $$n + \sqrt{n}$$ for indeterminate strings, where $$n$$ is the length of the prefix array. When we restrict ourselves to prefix arrays for partial words, we are able to bound the minimum alphabet size by $$\Big\lceil \sqrt{2n} \Big\rceil$$. Moreover, we show that this bound is tight up to a constant multiple by using Sidon sets.

We also study the relationship between border arrays and prefix arrays for partial words. We give necessary and sufficient conditions for a border array and prefix array to be satisfied by the same word, and we give an algorithm to enumerate all prefix arrays for partial words of a given length, $$n$$. This algorithm has a time complexity of $$n^2$$ times the output size, that is the number of valid prefix arrays for partial words of length $$n$$.