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.
Exact Learning of Primitive Formal Systems Defining Labeled Ordered Tree Languages via Queries
Tomoyuki UCHIDA Satoshi MATSUMOTO Takayoshi SHOUDAI Yusuke SUZUKI Tetsuhiro MIYAHARA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2019/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Full Text: PDF(1.1MB)>>
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.