Learning of erasing primitive formal systems from positive examples

• Published in: Theoretical computer science 2006-11, Vol.364 (1), p.98-114
• Main Authors: Uemura, Jin, Sato, Masako
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Artificial intelligence; Computer science; control theory; systems; Elementary formal system; Erasing pattern language; Exact sciences and technology; Inductive inference; Learning and adaptive systems; Positive example; Primitive formal system; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2006.07.043

The present paper considers the learning problem of erasing primitive formal systems, PFSs for short, in view of inductive inference in Gold framework from positive examples. A PFS is a kind of logic program over strings called regular patterns, and consists of exactly two axioms of the forms p ( π ) ← and p ( τ ) ← p ( x 1 ) , … , p ( x n ) , where p is a unary predicate symbol, π and τ are regular patterns, and x i s are distinct variables. A PFS is erasing or nonerasing according to allowing the empty string substitution for some variables or not. We investigate the learnability of the class P F S L of languages generated by the erasing PFSs satisfying a certain condition. We first show that the class P F S L has M-finite thickness. Moriyama and Sato showed that a language class with M-finite thickness is learnable if and only if there is a finite tell tale set for each language in the class. We then introduce a particular type of finite set of strings for each erasing PFS, and show that the set is a finite tell tale set of the language. These imply that the class P F S L is learnable from positive examples.