On indeterminate strings matching

P Gawrychowski, S Ghazawi… - 31st Annual Symposium …, 2020 - drops.dagstuhl.de
Given two indeterminate equal-length strings p and t with a set of characters per position in
both strings, we obtain a determinate string p_w from p and a determinate string t_w from t …

Hardness Results on Characteristics for Elastic-Degenerated Strings

D Köppl, J Olbrich - arxiv preprint arxiv:2411.10653, 2024 - arxiv.org
Generalizations of plain strings have been proposed as a compact way to represent a
collection of nearly identical sequences or to express uncertainty at specific text positions by …

[HTML][HTML] Computing covers using prefix tables

A Alatabbi, MS Rahman, WF Smyth - Discrete Applied Mathematics, 2016 - Elsevier
An indeterminate string x= x [1.. n] on an alphabet Σ is a sequence of nonempty subsets of Σ;
x is said to be regular if every subset is of size one. A proper substring u of regular x is said …

New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings

F Blanchet-Sadri, M Bodnar, B De Winkle - Theory of Computing Systems, 2017 - Springer
We extend earlier works on the relation of prefix arrays of indeterminate strings to undirected
graphs and border arrays. If integer array y is the prefix array for indeterminate string w, then …