Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data
スポンサーリンク
概要
- 論文の詳細を見る
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.
- (社)電子情報通信学会の論文
- 2009-02-01
著者
-
SUZUKI Yusuke
Graduate School of Fisheries Sciences, Hokkaido University
-
Uchida T
Graduate School Of Information Sciences Hiroshima City University
-
Shoudai T
Department Of Informatics Kyushu University
-
Shoudai Takayoshi
Department Of Control Engineering And Science Kyushu Institute Of Technology
-
TAKAMI Ryoji
Faculty of Information Sciences, Hiroshima City University
-
UCHIDA Tomoyuki
Graduate School of Information Sciences, Hiroshima City University
-
Takami Ryoji
Faculty Of Information Sciences Hiroshima City University
-
Suzuki Yusuke
Graduate School Of Information Sciences Hiroshima City University
-
Suzuki Yusuke
Graduate School Of Fisheries Sciences Hokkaido University
関連論文
- A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern
- Discovering Knowledge from Graph Structured Data by Using Refutably Inductive Inference of Formal Graph Systems (Special lssue on Selected Papers from LA Synposium)
- Energy content of the mysid Neomysis czerniawskii in Iwanai Bay, the coastal water of western Hokkaido
- Using Maximal Independent Sets to Solve Problems in Parallel
- Learning of Finite Unions of Tree Patterns with Internal Structured Variables from Queries
- Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data
- O(log^* n) Time Parallel Algorithm for Computing Bounded degree Maximal Subgraphs
- A P-Complete Language Describable with Iterated Shuffle
- A Parallel Algorithm for the Maximal Co-Hitting Set Problem