The search functionality is under construction.

The search functionality is under construction.

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}*,

- 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

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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}*,

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}*,

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}*,

ER -