Inferring an indeterminate string from a prefix graph

Ali Alatabbi, M. Sohel Rahman*, W. F. Smyth

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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 languageEnglish
Pages (from-to)6-13
Number of pages8
JournalJournal of Discrete Algorithms
Publication statusPublished - 1 May 2015


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


Dive into the research topics of 'Inferring an indeterminate string from a prefix graph'. Together they form a unique fingerprint.

Cite this