Parameterized Formal Graph Systems and Their Polynomial-Time PAC Learnability

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

doi:10.1587/transfun.2022EAP1052

IEICE TRANSACTIONS on Fundamentals

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-FGSL_k,_Δ(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-FGSL_k,_Δ(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-FGSL_k,_Δ(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

formal graph system, graph pattern, PAC learning, polynomial-time learnability

Cite this

Copy

Takayoshi SHOUDAI, Satoshi MATSUMOTO, Yusuke SUZUKI, Tomoyuki UCHIDA, Tetsuhiro MIYAHARA, "Parameterized Formal Graph Systems and Their Polynomial-Time PAC Learnability" in IEICE TRANSACTIONS on Fundamentals, vol. E106-A, no. 6, pp. 896-906, June 2023, doi: 10.1587/transfun.2022EAP1052.
Abstract: 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-FGSL_k,_Δ(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-FGSL_k,_Δ(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-FGSL_k,_Δ(m, s, t, r, w, d) is polynomial-time PAC learnable if all m, s, t, r, w, d, Δ are constants except for k.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022EAP1052/_p

Copy

@ARTICLE{e106-a_6_896,
author={Takayoshi SHOUDAI, Satoshi MATSUMOTO, Yusuke SUZUKI, Tomoyuki UCHIDA, Tetsuhiro MIYAHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Parameterized Formal Graph Systems and Their Polynomial-Time PAC Learnability},
year={2023},
volume={E106-A},
number={6},
pages={896-906},
abstract={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-FGSL_k,_Δ(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-FGSL_k,_Δ(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-FGSL_k,_Δ(m, s, t, r, w, d) is polynomial-time PAC learnable if all m, s, t, r, w, d, Δ are constants except for k.},
keywords={},
doi={10.1587/transfun.2022EAP1052},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Parameterized Formal Graph Systems and Their Polynomial-Time PAC Learnability
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 896
EP - 906
AU - Takayoshi SHOUDAI
AU - Satoshi MATSUMOTO
AU - Yusuke SUZUKI
AU - Tomoyuki UCHIDA
AU - Tetsuhiro MIYAHARA
PY - 2023
DO - 10.1587/transfun.2022EAP1052
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2023
AB - 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-FGSL_k,_Δ(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-FGSL_k,_Δ(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-FGSL_k,_Δ(m, s, t, r, w, d) is polynomial-time PAC learnable if all m, s, t, r, w, d, Δ are constants except for k.
ER -

IEICE TRANSACTIONS on Fundamentals