Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data

DOI Web Site 12 Citations 23 References

Search this article

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 g in ${\\cal TG_{TTSP}}$, the TTSP graph language of g, denoted by L(g), is the set of all TTSP graphs obtained from g by substituting arbitrary TTSP graphs for all variables in g. Firstly, when a TTSP graph G and a TTSP term graph g are given as inputs, we present a polynomial time matching algorithm which decides whether or not L(g) contains G. The minimal language problem for the class ${\\cal L_{TTSP}}=\\{L(g) \\mid g\\in {\\cal TG_{TTSP}}\\}$ is, given a set S of TTSP graphs, to find a TTSP term graph g in ${\\cal TG_{TTSP}}$ such that L(g) is minimal among all TTSP graph languages which contain all TTSP graphs in S. 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

Citations (12)*help

See more

References(23)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top