Inferring an indeterminate string from a prefix graph

Ali Alatabbi; M. Sohel Rahman; W. F. Smyth

doi:10.1016/j.jda.2014.12.006

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 journal › Article › peer-review

7 Citations (Scopus)

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[ⁱ¹] and x[ⁱ²] match (written x[ⁱ¹]≈x[ⁱ²]) if and only if x[ⁱ¹]∩x[ⁱ²]∗. 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	https://doi.org/10.1016/j.jda.2014.12.006
Publication status	Published - 1 May 2015

Keywords

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

Access to Document

10.1016/j.jda.2014.12.006

Cite this

@article{e03a1a7de3474625849d640ac054253d,

title = "Inferring an indeterminate string from a prefix graph",

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.",

keywords = "Degenerate string, Generalized string, Indeterminate string, Prefix graph, Prefix table, Reverse engineering, String",

author = "Ali Alatabbi and {Sohel Rahman}, M. and Smyth, {W. F.}",

year = "2015",

month = may,

day = "1",

doi = "10.1016/j.jda.2014.12.006",

language = "English",

volume = "32",

pages = "6--13",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

}

TY - JOUR

T1 - Inferring an indeterminate string from a prefix graph

AU - Alatabbi, Ali

AU - Sohel Rahman, M.

AU - Smyth, W. F.

PY - 2015/5/1

Y1 - 2015/5/1

N2 - 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.

AB - 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.

KW - Degenerate string

KW - Generalized string

KW - Indeterminate string

KW - Prefix graph

KW - Prefix table

KW - Reverse engineering

KW - String

UR - http://www.scopus.com/inward/record.url?scp=84925354426&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2014.12.006

DO - 10.1016/j.jda.2014.12.006

M3 - Article

AN - SCOPUS:84925354426

SN - 1570-8667

VL - 32

SP - 6

EP - 13

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

ER -

Inferring an indeterminate string from a prefix graph

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this