Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Inferring an indeterminate string from a prefix graph

Alatabbi, A., Sohel Rahman, M. and Smyth, W.F. (2014) Inferring an indeterminate string from a prefix graph. Journal of Discrete Algorithms, 32 . pp. 6-13.

PDF - Authors' Version
Download (360kB)
Link to Published Version:
*Subscription may be required


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.

Item Type: Journal Article
Murdoch Affiliation(s): School of Engineering and Information Technology
Publisher: Elsevier
Copyright: © 2014 Elsevier B.V.
Item Control Page Item Control Page


Downloads per month over past year