Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data

Ryoji TAKAMI  Yusuke SUZUKI  Tomoyuki UCHIDA  Takayoshi SHOUDAI  

IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.2   pp.181-190
Publication Date: 2009/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.181
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
inductive inference,  computational learning theory,  TTSP graph,  graph languages,  

Full Text: PDF(1.2MB)>>
Buy this Article

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.