PT Unknown AU Manea, FS Mercaş, R Schmid, M Fernau, H TI Efficient Computation of Descriptive Patterns SE Bericht des Instituts für Informatik PY 1992 VL 1405 PU Institut für Informatik WP https://macau.uni-kiel.de/receive/macau_mods_00001788 LA en SN 2192-6247 AB 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. PI Kiel ER