You are provided with the abstract of a scientific paper and the abstracts of the papers it references. Your task is to write a Related Work section for the main paper. This section should concisely summarize and integrate the key points from the cited abstracts, reflecting how they relate to the main paper's contributions and context. In your summary, use numerical citation markers like [1], [2], etc., to refer to the corresponding papers.

Main Abstract:
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 notably in data mining, computational biology, and in understanding the complexity of genetic algorithms. We show that the basic problem of finding a small set of patterns that match one set of strings but do not match any string in a second set is difficult (NP-complete, W[2]-hard when parameterized by the size of the pattern set, and APX-hard). We then perform a detailed parameterized analysis of the problem, separating tractable and intractable variants. In particular we show that parameterizing by the size of pattern set and the number of strings, and the size of the alphabet and the number of strings give FPT results, amongst others.

Cited Abstract(s):
[1]: This chapter focuses on a polynomial-time algorithm for learning k -variable pattern languages in the learning model introduced by Valiant for each constant k . A pattern is a string of constant and variable symbols. For any constant k , the algorithm learns a k -variable target pattern p by producing a polynomial-sized disjunction of patterns, each of between 0 and k variables. The algorithm allows empty substitutions and can be extended to handle restricted homomorphisms on the substitution strings. It is assumed that the algorithm has access to a random source of negative examples, generated according to an arbitrary distribution, and a random source of positive examples of the target pattern p in which the k -tuple of substitution strings is drawn not from an arbitrary distribution but from any product distribution.

[2]: Abstract Assume a finite alphabet of constant symbols and a disjoint infinite alphabet of variable symbols . A pattern is a non-null finite string of constant and variable symbols. The language of a pattern is all strings obtainable by substituting non-null strings of constant symbols for the variables of the pattern. A sample is a finite nonempty set of non-null strings of constant symbols. Given a sample S , a pattern p is descriptive of S provided the language of p contains S and does not properly contain the language of any other pattern that contains S . The computational problem of finding a pattern descriptive of a given sample is studied. The main result is a polynomial-time algorithm for the special case of patterns containing only one variable symbol (possibly occurring several times in the pattern). Several other results are proved concerning the class of languages generated by patterns and the problem of finding a descriptive pattern.
One of most immediately similar variants is that where pattern variables are allowed. In contrast to the work here, these variables can act as substrings of arbitrary length. Keans and Pitt [1] give a family of polynomial time algorithms for learning the language generated by a single such pattern with a given number @math of pattern variables. Angluin [2] studies the inverse problem of generating a pattern, with a polynomial time algorithm for the case where the pattern contains a single pattern variable being the central result. We note that a central difference here is the repeated use of variables, allowing the same undefined substring to be repeated. The properties of these pattern languages have since been studied in some detail, far beyond the scope of this paper.