## Abstract

An indeterminate string (or, more simply, just a string) x=x[1.n] on an alphabet Σ is a sequence of nonempty subsets of Σ. We say that x[^{i1}] and x[^{i2}] match (written x[^{i1}]≈x[^{i2}]) if and only if x[^{i1}]∩x[^{i2}]∗. A feasible array is an array y=y[1.n] of integers such that y[1]=n and for every i∈2.n, y[i]∈0.n-i+1. A prefix table of a string x is an array π=π[1.n] of integers such that, for every i∈1.n, π[i]=j if and only if 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=^{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 ^{Py} to construct a lexicographically least indeterminate string on a minimum alphabet whose prefix table π=y.

Original language | English |
---|---|

Pages (from-to) | 6-13 |

Number of pages | 8 |

Journal | Journal of Discrete Algorithms |

Volume | 32 |

DOIs | |

Publication status | Published - 1 May 2015 |

## Keywords

- Degenerate string
- Generalized string
- Indeterminate string
- Prefix graph
- Prefix table
- Reverse engineering
- String