The search functionality is under construction.
The search functionality is under construction.

Parameterized Formal Graph Systems and Their Polynomial-Time PAC Learnability

Takayoshi SHOUDAI, Satoshi MATSUMOTO, Yusuke SUZUKI, Tomoyuki UCHIDA, Tetsuhiro MIYAHARA

  • Full Text Views

    9

  • Cite this

Summary :

A formal graph system (FGS for short) is a logic program consisting of definite clauses whose arguments are graph patterns instead of first-order terms. The definite clauses are referred to as graph rewriting rules. An FGS is shown to be a useful unifying framework for learning graph languages. In this paper, we show the polynomial-time PAC learnability of a subclass of FGS languages defined by parameterized hereditary FGSs with bounded degree, from the viewpoint of computational learning theory. That is, we consider VH-FGSLk,Δ(m, s, t, r, w, d) as the class of FGS languages consisting of graphs of treewidth at most k and of maximum degree at most Δ which is defined by variable-hereditary FGSs consisting of m graph rewriting rules having TGP patterns as arguments. The parameters s, t, and r denote the maximum numbers of variables, atoms in the body, and arguments of each predicate symbol of each graph rewriting rule in an FGS, respectively. The parameters w and d denote the maximum number of vertices of each hyperedge and the maximum degree of each vertex of TGP patterns in each graph rewriting rule in an FGS, respectively. VH-FGSLk,Δ(m, s, t, r, w, d) has infinitely many languages even if all the parameters are bounded by constants. Then we prove that the class VH-FGSLk,Δ(m, s, t, r, w, d) is polynomial-time PAC learnable if all m, s, t, r, w, d, Δ are constants except for k.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.6 pp.896-906
Publication Date
2023/06/01
Publicized
2022/12/14
Online ISSN
1745-1337
DOI
10.1587/transfun.2022EAP1052
Type of Manuscript
PAPER
Category
Algorithms and Data Structures

Authors

Takayoshi SHOUDAI
  Fukuoka Institute of Technology
Satoshi MATSUMOTO
  Tokai University
Yusuke SUZUKI
  Hiroshima City University
Tomoyuki UCHIDA
  Hiroshima City University
Tetsuhiro MIYAHARA
  Hiroshima City University

Keyword