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

Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data

Ryoji TAKAMI, Yusuke SUZUKI, Tomoyuki UCHIDA, Takayoshi SHOUDAI

  • Full Text Views

    0

  • Cite this

Summary :

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 TGTTSP be the set of all TTSP term graphs whose variable labels are mutually distinct. For a TTSP term graph g in TGTTSP, 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 LTTSP={L(g) | gTGTTSP} is, given a set S of TTSP graphs, to find a TTSP term graph g in TGTTSP 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 LTTSP. Finally, we show that LTTSP is polynomial time inductively inferable from positive data.

Publication
IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.181-190
Publication Date
2009/02/01
Publicized
Online ISSN
1745-1361
DOI
10.1587/transinf.E92.D.181
Type of Manuscript
Special Section PAPER (Special Section on Foundations of Computer Science)
Category

Authors

Keyword