Exact Learning of Primitive Formal Systems Defining Labeled Ordered Tree Languages via Queries

Tomoyuki UCHIDA  Satoshi MATSUMOTO  Takayoshi SHOUDAI  Yusuke SUZUKI  Tetsuhiro MIYAHARA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.470-482
Publication Date: 2019/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018FCP0011
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Category: 
Keyword: 


Full Text: PDF(1.1MB)
>>Buy this Article


Summary: 
A formal graph system (FGS) is a logic programming system that directly manipulates graphs by dealing with graph patterns instead of terms of first-order predicate logic. In this paper, based on an FGS, we introduce a primitive formal ordered tree system (pFOTS) as a formal system defining labeled ordered tree languages. A pFOTS program is a finite set of graph rewriting rules. A logic program is well-known to be suitable to represent background knowledge. The query learning model is an established mathematical model of learning via queries in computational learning theory. In this learning model, we show the exact learnability of a pFOTS program consisting of one graph rewriting rule and background knowledge defined by a pFOTS program using a polynomial number of queries.