Indeterminate strings, prefix arrays \& undirected graphs

DOI10.1016/J.TCS.2015.06.056zbMATH Open1329.68309arXiv1406.3289OpenAlexW1541587921MaRDI QIDQ496001FDOQ496001

Patrick J. Ryan, Shu Wang, Manolis Christodoulakis, W. F. Smyth

Publication date: 16 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1406.3289

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

zbMATH Keywords

undirected graphlexicographical orderfeasible arrayindeterminate stringminimum alphabet sizeprefix arrayprefix tableregular string

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Algorithms on strings (68W32)

Cites Work

• Algorithm 457: finding all cliques of an undirected graph
• Graph theory
• Depth-First Search and Linear Graph Algorithms
• Sur le coloriage des graphs
• Title not available (Why is that?)
• On cliques in graphs
• Title not available (Why is that?)
• An O(n log n) algorithm for finding all repetitions in a string
• Generalized String Matching
• Algorithms on Strings
• Prefix Table Construction and Conversion
• An adaptive hybrid pattern-matching algorithm on indeterminate strings
• Algorithmic Combinatorics on Partial Words
• REVERSE ENGINEERING PREFIX TABLES
• A new approach to the periodicity lemma on strings with holes
• Fast pattern-matching on indeterminate strings
• Title not available (Why is that?)
• Border array on bounded alphabet
• RECONSTRUCTING A SUFFIX ARRAY
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2003
• Partial words and a theorem of Fine and Wilf revisited
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

• Universal reconstruction of a string
• An improved upper bound and algorithm for clique covers
• Universal Reconstruction of a String
• Computing covers using prefix tables
• Border correlations, lattices, and the subgraph component polynomial
• A new approach to regular \& indeterminate strings
• New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings
• Constructing an indeterminate string from its associated graph
• Reconstructing a string from its Lyndon arrays
• A prefix array for parameterized strings
• Inferring an indeterminate string from a prefix graph
• Border Correlations, Lattices, and the Subgraph Component Polynomial

Uses Software

• Algorithm 457

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)