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

Indeterminate strings, prefix arrays & undirected graphs

Christodoulakis, M., Ryan, P.J., Smyth, W.F. and Wang, S. (2015) Indeterminate strings, prefix arrays & undirected graphs. Theoretical Computer Science, 600 . pp. 34-48.

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


An integer array y=y[1..n] is said to be feasible if and only if y[1]=n and, for every i∈2..n, i≤i+y[i]≤n+1. A string is said to be indeterminate if and only if at least one of its elements is a subset of cardinality greater than one of a given alphabet Σ; otherwise it is said to be regular. A feasible array y is said to be regular if and only if it is the prefix array of some regular string. We show using a graph model that every feasible array of integers is a prefix array of some (indeterminate or regular) string, and for regular strings corresponding to y, we use the model to provide a lower bound on the alphabet size. We show further that there is a 1–1 correspondence between labelled simple graphs and indeterminate strings, and we show how to determine the minimum alphabet size σ of an indeterminate string x based on its associated graph Gx. Thus, in this sense, indeterminate strings are a more natural object of combinatorial interest than the strings on elements of Σ that have traditionally been studied.

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


Downloads per month over past year