正規パターン言語の和集合の質問学習
スポンサーリンク
概要
- 論文の詳細を見る
A pattern is a finite string consisting of constant symbols and variables. A pattern in which each variable appears at most once is called a regular pattern. The language of a pattern is the set of all strings obtained by substituting non-empty strings of constant symbols for each variable. The language of a regular pattern is called a regular pattern language. For the erasing pattern language of a pattern, it is admissible to substitute the empty string for variables. The erasing pattern language of a regular pattern is called an erasing regular pattern language. In this paper, we show that the class of unions of at most k regular pattern languages is learnable in O(kl^2) time using at most k + 1 equivalence queries and at most k(2l - 1) restricted subset queries, where l is the maximum length of counterexamples. Moreover, we show that the class of unions of at most k erasing regular pattern languages is learnable in O(kl^2) time using at most k + 1 equivalence queries and at most k(2l + 1) restricted subset queries.
- 東海大学の論文
- 2004-03-30
著者
関連論文
- 繰り返し内部構造変数を持つ木パターンの有限和の質問学習
- 高さ制約変数を持つ順序木パターン言語の正データからの多項式時間帰納推論可能性について
- Polynomial Time Learnabilities of Tree Patterns with Internal Structured Variables from Queries (New Aspects of Theoretical Computer Science)
- Polynomial Time Inductive Inference of Ordered Term Trees with Contractible Variables from Positive Data (New Aspects of Theoretical Computer Science)
- Learning of Elementary Formal Systems with Two Clauses using Queries and Their Languages(New Trends in Theory of Computation and Algorithm)
- 内部変数付き木パターン言語の有限和の質問学習
- 質問学習における学習可能性の統一的特徴づけ
- Learning pattern languages using queries
- Learnability of Subsequence Languages
- 順序付き二分法定グラフの学習可能性
- 反駁PAC学習可能性
- Polynomial time inductive inference of unions of two term tree languages (特集 「人と技術とAI」および一般)
- 正規パターン言語の和集合の質問学習
- 項グラフ言語の正データからの多項式時間帰納推論可能性について(計算理論とその応用)
- 項グラフ言語の正データからの多項式時間帰納推論可能性について