Indeterminate strings, prefix arrays \& undirected graphs
From MaRDI portal
Abstract: An integer array y = y[1..n] is said to be feasible if and only if y[1] = n and, for every i in 2..n, i le i+y[i] le 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 Sigma; 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 |Sigma| 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 Sigma that have traditionally been studied.
Recommendations
- Inferring an indeterminate string from a prefix graph
- New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings
- New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings
- A new approach to regular \& indeterminate strings
- Constructing an indeterminate string from its associated graph
Cites work
- scientific article; zbMATH DE number 3471577 (Why is no real title available?)
- scientific article; zbMATH DE number 2052918 (Why is no real title available?)
- scientific article; zbMATH DE number 2183071 (Why is no real title available?)
- scientific article; zbMATH DE number 1874382 (Why is no real title available?)
- scientific article; zbMATH DE number 5263622 (Why is no real title available?)
- scientific article; zbMATH DE number 3259991 (Why is no real title available?)
- A new approach to the periodicity lemma on strings with holes
- Algorithm 457: finding all cliques of an undirected graph
- Algorithmic Combinatorics on Partial Words
- Algorithms on Strings
- An O(n log n) algorithm for finding all repetitions in a string
- An adaptive hybrid pattern-matching algorithm on indeterminate strings
- Border array on bounded alphabet
- Depth-First Search and Linear Graph Algorithms
- Fast pattern-matching on indeterminate strings
- Generalized String Matching
- Graph theory
- Mathematical Foundations of Computer Science 2003
- On cliques in graphs
- Partial words and a theorem of Fine and Wilf revisited
- Prefix table construction and conversion
- RECONSTRUCTING A SUFFIX ARRAY
- Reverse engineering prefix tables
- Sur le coloriage des graphs
Cited in
(14)- Universal reconstruction of a string
- Universal reconstruction of a string
- An improved upper bound and algorithm for clique covers
- New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings
- Computing covers using prefix tables
- Indeterminate string inference algorithms
- Border correlations, lattices, and the subgraph component polynomial
- Border correlations, lattices, and the subgraph component polynomial
- A new approach to regular \& indeterminate strings
- Constructing an indeterminate string from its associated graph
- Reconstructing a string from its Lyndon arrays
- New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings
- A prefix array for parameterized strings
- Inferring an indeterminate string from a prefix graph
This page was built for publication: Indeterminate strings, prefix arrays \& undirected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496001)
