| 作成者 |
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
A pattern is a finite string of constant symbols and variable symbols. The language of a pattern is the set of all strings obtained by substituting any non-null constant string for each variable symbo...l in the pattern. A pattern language was introduced by Angluin in 1979 as a concrete class of languages which is inferable from positive data. In this paper, we consider the decision problem, whether for given two patterns there is a containment relation between their pattern languages, which was posed by Angluin and remains open. We give some sufficient conditions to make this problem decidable. We introduce the notions of a generalization, an instance, a minimal generalization and a maximal instance for a set of patterns. We also show that a set of patterns with a same length forms a lattice under the operations which take a minimal generalization and a maximal instance. Further, we characterize the above open problem using the minimal generalization.続きを見る
|
Mendeley出力
rifis-tr-41