Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data

Access this Article

Search this Article

Author(s)

Abstract

Two-Terminal Series Parallel (TTSP, for short) graphs are used as data models in applications for electric networks and scheduling problems. We propose a TTSP term graph which is a TTSP graph having structured variables, that is, a graph pattern over a TTSP graph. Let${\\cal TG_{TTSP}}$ be the set of all TTSP term graphs whose variable labels are mutually distinct. For a TTSP term graph <i>g</i> in ${\\cal TG_{TTSP}}$, the TTSP graph language of <i>g</i>, denoted by <i>L</i>(<i>g</i>), is the set of all TTSP graphs obtained from <i>g</i> by substituting arbitrary TTSP graphs for all variables in <i>g</i>. Firstly, when a TTSP graph <i>G</i> and a TTSP term graph <i>g</i> are given as inputs, we present a polynomial time matching algorithm which decides whether or not <i>L</i>(<i>g</i>) contains <i>G</i>. The minimal language problem for the class ${\\cal L_{TTSP}}=\\{L(g) \\mid g\\in {\\cal TG_{TTSP}}\\}$ is, given a set <i>S</i> of TTSP graphs, to find a TTSP term graph <i>g</i> in ${\\cal TG_{TTSP}}$ such that <i>L</i>(<i>g</i>) is minimal among all TTSP graph languages which contain all TTSP graphs in <i>S</i>. Secondly, we give a polynomial time algorithm for solving the minimal language problem for ${\\cal L_{TTSP}}$. Finally, we show that ${\\cal L_{TTSP}}$ is polynomial time inductively inferable from positive data.

Journal

  • IEICE Transactions on Information and Systems

    IEICE Transactions on Information and Systems 92(2), 181-190, 2009-02-01

    The Institute of Electronics, Information and Communication Engineers

References:  13

Codes

Page Top