Efficient Computation of Descriptive Patterns

zum Volltext (860 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • Mai 2014
Seitenbereich32 S.

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.
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000026
IDNummer des Berichts :
  • TR_1405