<テクニカルレポート>
Characterization of Pattern Languages

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 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.続きを見る

本文情報を非表示

rifis-tr-41 pdf 961 KB 68  

詳細

レコードID
査読有無
関連情報
注記
タイプ
登録日 2009.04.22
更新日 2017.01.20