Inferring an indeterminate string from a prefix graph

An indeterminate string (or, more simply, just a string  ) x=x[1..n]x=x[1..n] on an alphabet Σ is a sequence of nonempty subsets of Σ  . We say that x[i1]x[i1] and x[i2]x[i2]match   (written x[i1]≈x[i2]x[i1]≈x[i2]) if and only if x[i1]∩x[i2]≠∅x[i1]∩x[i2]≠∅. A feasible array   is an array y=y[1..n]y=y[1..n] of integers such that y[1]=ny[1]=n and for every i∈2..ni∈2..n, y[i]∈0..n−i+1y[i]∈0..n−i+1. A prefix table of a string x   is an array π=π[1..n]π=π[1..n] of integers such that, for every i∈1..ni∈1..n, π[i]=jπ[i]=j if and only if x[i..i+j−1]x[i..i+j−1] is the longest substring at position i of x that matches a prefix of x. It is known from [6] that every feasible array is a prefix table of some indeterminate string. A prefix graph  P=PyP=Py is a labelled simple graph whose structure is determined by a feasible array y. In this paper we show, given a feasible array y  , how to use PyPy to construct a lexicographically least indeterminate string on a minimum alphabet whose prefix table π=yπ=y.