Journal article
Inferring an indeterminate string from a prefix graph
Journal of Discrete Algorithms, Vol.32, pp.6-13
2014
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.
Details
- Title
- Inferring an indeterminate string from a prefix graph
- Authors/Creators
- A. Alatabbi (Author/Creator) - King's College LondonM. Sohel Rahman (Author/Creator)W.F. Smyth (Author/Creator) - Murdoch University
- Publication Details
- Journal of Discrete Algorithms, Vol.32, pp.6-13
- Publisher
- Elsevier
- Identifiers
- 991005541177407891
- Copyright
- © 2014 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
118 File views/ downloads
58 Record Views