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

*Subscription may be required

## Abstract

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.

Publication Type: | Journal Article |
---|---|

Murdoch Affiliation: | School of Engineering and Information Technology |

Publisher: | Elsevier BV |

Copyright: | © 2015 Elsevier B.V. |

URI: | http://researchrepository.murdoch.edu.au/id/eprint/27493 |

Item Control Page |