Inferring an indeterminate string from a prefix graph

Abstract: An itbf{indeterminate string} (or, more simply, just a itbf{string})

s x = s x [1.. n]

on an alphabet

S i g m a

is a sequence of nonempty subsets of

S i g m a

. We say that

s x [i_{1}]

and

s x [i_{2}]

itbf{match} (written

s x [i_{1}] m a t c h s x [i_{2}]

) if and only if

s x [i_{1}] c a p s x [i_{2}] e e m p t y s e t

. A itbf{feasible array} is an array

s y = s y [1.. n]

of integers such that

s y [1] = n

and for every

i i n 2.. n

,

s y [i] i n 0.. n - i + 1

. A itbf{prefix table} of a string

s x

is an array

s p i = s p i [1.. n]

of integers such that, for every

i i n 1.. n

,

s p i [i] = j

if and only if

s x [i .. i + j - 1]

is the longest substring at position

i

of s{x} that matches a prefix of s{x}. It is known from cite{CRSW13} that every feasible array is a prefix table of some indetermintate string. A itbf{prefix graph}

m a t h c a l P = m a t h c a l P_{s y}

is a labelled simple graph whose structure is determined by a feasible array s{y}. In this paper we show, given a feasible array s{y}, how to use

m a t h c a l P_{s y}

to construct a lexicographically least indeterminate string on a minimum alphabet whose prefix table

s p i = s y

.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Inferring an indeterminate string from a prefix graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2343296)