<テクニカルレポート>
Learning One-Variable Pattern Languages in Linear Average Time

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 A new algorithm for learning one-variable pattern languages is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all operatio...ns till an algorithm has converged to a correct hypothesis. For the expectation it is shown that for almost all meaningful distributions defining how the pattern variable is replaced by a string to generate random samples of the target pattern language this algorithm converges within a constant number of rounds with a total learning time that is linear in the pattern length. Thus, the algorithm is average-case optimal in a strong sense.続きを見る

本文情報を非表示

trcs140.ps gz 172 KB 38  
trcs140 pdf 369 KB 101  

詳細

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