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