Efficient Computation of Descriptive Patterns
A pattern $\alpha$ is a word consisting of constants and variables and the pattern language $L(\alpha)$ (over an alphabet $\Sigma$) is the set of all words that can be obtained from $\alpha$ by uniformly replacing the variables with words over $\Sigma$. We investigate the problem of computing a pattern $\alpha$ that is descriptive of a given finite set $S \subseteq \Sigma^*$ of words, i.\,e., $S \subseteq L(\alpha)$ and there is no other pattern $\beta$ with $S \subseteq L(\beta) \subset L(\alpha)$. A pattern $\alpha$ that is descriptive of a set $S$ represents the structural commonalities of the words in $S$ and, thus, can serve as a classifier with respect to this structure. Furthermore, (polynomial time) computability of descriptive patterns is sufficient for (polynomial time) inductive inference of pattern languages. We investigate the complexity of computing descriptive patterns and, for subclasses of patterns, we present efficient algorithms for computing them.