000K utf8 1100 $c2014 1500 eng 2050 urn:nbn:de:101:1-201405125349 3000 Manea, Florin Silviu 3010 Fernau, Henning 3010 Mercaş, Robert 3010 Schmid, Markus 4000 Efficient Computation of Descriptive Patterns [Manea, Florin Silviu] 4209 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. 4950 https://nbn-resolving.org/urn:nbn:de:101:1-201405125349$xR$3Volltext$534 4961 https://macau.uni-kiel.de/receive/macau_mods_00001788 5051 004