## ＜テクニカルレポート＞Efficient learning of One-Variable Patttern Languages From Positive Data

作成者 作成者名 所属機関 所属機関名 Institut für Infonnatik, Technische Universität München 所属機関 所属機関名 Institut für Infonnatik, Technische Universität München 作成者名 所属機関 所属機関名 Institut für Infonnatik, Technische Universität München 作成者名 所属機関 所属機関名 Institut für Infonnatik, Technische Universität München 作成者名 所属機関 所属機関名 Department of Informatics Kyushu University 英語 Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院情報理学部門 1996-12-12 128 Accepted Manuscript open access DOI Technical Report || 128 http://www.i.kyushu-u.ac.jp/research/report.html A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting ...non-empty strings for variables. Descriptive patterns are a key concept for inductive inference of pattern languages. A pattern \$ pi \$ is descriptive for a given sample if the sample is contained in the language \$ L(pi) \$ generated by \$ pi \$ and no other pattern having this property generates a proper subset of the language \$ L(pi) \$. The best previously known algorithm for computing descriptive one-variable patterns requires time \$ O(n^4 log n) \$, where \$ n \$ is the size of the sample. We present a simpler and more efficient algorithm solving the same problem in time \$ O(n^2 log n) \$. In addition, we give a parallel version of this algorithm that requires time \$ O(log n) \$ and \$ O(n^3log n) \$ processors on an EREW-PRAM. Previously, no parallel algorithm was known for this problem. Using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is \$ O(l^2log l) \$ provided the sample strings are drawn from the target language according to a probability distribution with expected string length \$ l \$. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Furthermore, we show how the algorithm for descriptive onevariable patterns can be used for learning one-variable patterns with a polynomial number of superset queries.続きを見る

### 本文ファイル

trcs128 pdf 439 KB 68
trcs128.ps gz 257 KB 58

### 詳細

レコードID 3003 査読無 テクニカルレポート 2009.04.22 2014.08.26