Separating Sets of Strings by Finding Matching Patterns is Almost Always Hard

Giuseppe Lancia, Luke Mathieson, Pablo Moscato

We study the complexity of the problem of searching for a set of patterns that separate two given sets of strings. This problem has applications in a wide variety of areas, most no…