Inferring an Indeterminate String from a Prefix Graph

An \itbf{indeterminate string} (or, more simply, just a \itbf{string}) $\s{x} = \s{x}[1…n]$onanalphabet$\Sigma$isasequenceofnonemptysubsetsof$\Sigma$\mathrm{.}Wesaythat$\s{x}[i_1]$and$\s{x}[i_2]$bfmatch(written$\s{x}[i_1] \match \s{x}[i_2]$)ifandonlyif$\s{x}[i_1] \cap \s{x}[i_2] \ne \emptyset$\mathrm{.}Abffeasiblearrayisanarray$\s{y} = \s{y}[1…n]$ of integers such that $\text{s}y[1]=n$ and for every $i\in \mathrm{2..}n$, $\s{y}[i] \in 0…n- i+ 1$\mathrm{.}Abfprefixtableofastring$\s{x}$isanarray$\s{\pi} = \s{\pi}[1…n]$ofintegerssuchthat,forevery$i \in 1…n$,$\s{\pi}[i] = j$ifandonlyif$\s{x}[i…i+ j- 1]$isthelongestsubstringatposition$i$ of \s{x} that matches a prefix of \s{x}. It is known from \cite{CRSW13} that every feasible array is a prefix table of some indetermintate string. A \itbf{prefix graph} $\mathcal{P}={\mathcal{P}}_{\text{s}y}$ is a labelled simple graph whose structure is determined by a feasible array \s{y}. In this paper we show, given a feasible array \s{y}, how to use ${\mathcal{P}}_{\text{s}y}$ to construct a lexicographically least indeterminate string on a minimum alphabet whose prefix table $\text{s}\pi =\text{s}y$.