Takami, Ryoji; Suzuki, Yusuke; Uchida, Tomoyuki; Shoudai, Takayoshi; Nakamura, Yasuaki Polynomial time inductive inference of TTSP graph languages from positive data. (English) Zbl 1134.68379 Kramer, Stefan (ed.) et al., Inductive logic programming. 15th international conference, ILP 2005, Bonn, Germany, August 10–13, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28177-0/pbk). Lecture Notes in Computer Science 3625. Lecture Notes in Artificial Intelligence, 366-383 (2005). 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 \(\mathcal{TG}_{\mathcal{TTSP}}\) be the set of all TTSP term graphs whose variable labels are mutually distinct. For a TTSP term graph \(g\), 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 \(\mathcal{L}_{\mathcal{TTSP}} = \{L(g) \mid g \in \mathcal{TG}_{\mathcal{TTSP}}\}\) is, given a set \(S\) of TTSP graphs, to find a TTSP term graph \(g\) in \(\mathcal{TG}_{\mathcal{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 \(\mathcal{L}_{\mathcal{TTSP}}\). Finally, we show that \(\mathcal{L}_{\mathcal{TTSP}}\) is polynomial time inductively inferable from positive data.For the entire collection see [Zbl 1087.68006]. Cited in 5 Documents MSC: 68Q32 Computational learning theory 68Q45 Formal languages and automata PDFBibTeX XMLCite \textit{R. Takami} et al., Lect. Notes Comput. Sci. 3625, 366--383 (2005; Zbl 1134.68379) Full Text: DOI