The Prague Stringology Conference 2008

Pavlos Antoniou, Maxime Crochemore, Costas S. Iliopoulos, Inuka Jayasekera and Gad M. Landau

Conservative String Covering of Indeterminate Strings

We study the problem of finding local and global covers as well as seeds in conservative indeterminate strings. An indeterminate string is a sequence T=T[1]T[2]...T[n], where T[i] ⊆ Σ for each i, and Σ is a given alphabet of fixed size. A conservative indeterminate string, is an indeterminate string where the number of indeterminate symbols in the positions of the string, i.e. the non-solid symbols, is bounded by a constant κ. We present an algorithm for finding a conservative indeterminate pattern p in an indeterminate string t. Furthermore, we present algorithms for computing conservative coversand seeds of the string t.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation