Journal article
Indeterminate strings, prefix arrays & undirected graphs
Theoretical Computer Science, Vol.600, pp.34-48
2015
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.
Details
- Title
- Indeterminate strings, prefix arrays & undirected graphs
- Authors/Creators
- M. Christodoulakis (Author/Creator)P.J. Ryan (Author/Creator)W.F. Smyth (Author/Creator)S. Wang (Author/Creator)
- Publication Details
- Theoretical Computer Science, Vol.600, pp.34-48
- Publisher
- Elsevier BV
- Identifiers
- 991005541678307891
- Copyright
- © 2015 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
107 File views/ downloads
67 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Industry collaboration
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science