Algorithmic Learning Theory with Elementary Formal Systems

Setsuo ARIKAWA  Satoru MIYANO  Ayumi SHINOHARA  Takeshi SHINOHARA  Akihiro YAMAMOTO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.4   pp.405-414
Publication Date: 1992/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Issue on Algorithmic Learning Theory)
Category: 
Keyword: 
algorithmic learning theory,  computational learning theory,  elementary formal system,  

Full Text: PDF(936.2KB)
>>Buy this Article


Summary: 
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.