Inferring an indeterminate string from a prefix graph

DOI10.1016/j.jda.2014.12.006zbMath1328.68320arXiv1502.07870OpenAlexW3100960033MaRDI QIDQ2343296

W. F. Smyth, M. Sohel Rahman, Ali Alatabbi

Publication date: 4 May 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

reverse engineeringindeterminate stringprefix tablegeneralized stringdegenerate stringprefix graph

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items

Universal Reconstruction of a String, Computing covers using prefix tables, Reconstructing a string from its Lyndon arrays, Constructing an indeterminate string from its associated graph, A new approach to regular \& indeterminate strings, IDPM: An Improved Degenerate Pattern Matching Algorithm for Biological Sequences, A prefix array for parameterized strings, Universal reconstruction of a string

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Indeterminate string inference algorithms
• Indeterminate strings, prefix arrays \& undirected graphs
• A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching
• Counting distinct strings
• Prefix Table Construction and Conversion
• Linear Time Inference of Strings from Cover Arrays Using a Binary Alphabet
• New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings
• An O(n log n) algorithm for finding all repetitions in a string
• RECONSTRUCTING A SUFFIX ARRAY
• Generalized String Matching
• Algorithmic Combinatorics on Partial Words
• REVERSE ENGINEERING PREFIX TABLES
• Mathematical Foundations of Computer Science 2003