Learning One-Variable Pattern Languages in Linear Average Time - Collections

＜technical report＞
Learning One-Variable Pattern Languages in Linear Average Time

Creator	Creator Name Reischuk, Rüdiger Affiliation Affiliation Name Institut für Theoretische Informatik Med. Universität zu Lübeck
Creator	Creator Name Zeugmann, Thomas Affiliation Affiliation Name Department of Informatics Kyushu University
Language	English
Publisher	Department of Informatics, Kyushu University
Publisher	九州大学大学院システム情報科学研究院情報理学部門
Date	1997-09-30
Source Title	DOI Technical Report
Vol	140
Publication Type	Accepted Manuscript
Access Rights	open access
Related DOI	DOI Technical Report \|\| 140
Related DOI	http://www.i.kyushu-u.ac.jp/research/report.html
Related URI	DOI Technical Report \|\| 140
Related URI	http://www.i.kyushu-u.ac.jp/research/report.html
Relation	DOI Technical Report \|\| 140
Relation	http://www.i.kyushu-u.ac.jp/research/report.html
Abstract	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.show more

File	FileType	Size	Views	Description
trcs140.ps	gz	172 KB	64
trcs140	pdf	369 KB	165