For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Algorithmic Learning Theory with Elementary Formal Systems
Setsuo ARIKAWA Satoru MIYANO Ayumi SHINOHARA Takeshi SHINOHARA Akihiro YAMAMOTO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/07/25
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Issue on Algorithmic Learning Theory)
algorithmic learning theory, computational learning theory, elementary formal system,
Full Text: PDF(936.2KB)
>>Buy this Article
The elementary formal system (EFS, for short) is a kind of logic program which directly manipulates character strings. This paper outlines in brief the authors' studies on algorithmic learning theory developed in the framework of EFS's. We define two important classes of EFS's and a new hierarchy of various language classes. Then we discuss EFS's as logic programs. We show that EFS's form a good framework for inductive inference of languages by presenting model inference system for EFS's in Shapiro's sense. Using the framework we also show that inductive inference from positive data and PAC-learning are both much more powerful than they have been believed. We illustrate an application of our theoretical results to Molecular Biology.