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

Access this Article

Author(s)

Abstract

<p>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.</p>

Journal

  • IEICE Transactions on Information and Systems

    IEICE Transactions on Information and Systems E102.D(3), 470-482, 2019

    The Institute of Electronics, Information and Communication Engineers

Codes

Page Top