Polynomial Time Inductive Inference of Cograph Pattern Languages from Positive Data
Polynomial Time Inductive Inference of Cograph Pattern Languages from Positive Data
复制标题
正数据的 Cograph 模式语言的多项式时间归纳推理
DOI：
10.1007/978-3-642-31951-8_32
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
T.Miyahara
中科院分区：
文献类型：
--
作者：
Y.Yoshimura;T.Shoudai;Y.Suzuki;T.Uchida;T.Miyahara
上图（互补可约图）是一个可以通过对图进行不交并和互补操作而生成的图，从单个顶点图开始。共图在计算机科学的许多领域都有广泛的研究，为了开发一种有效的图结构数据挖掘方法，本文介绍了一种图模式表达式，称为共图模式，它是具有结构变量的一种特殊类型的共图。首先，我们提出了一个多项式时间的上图模式匹配算法。其次，我们给出了一个多项式时间算法，以获得一个最小广义上图模式，解释给定的正数据。最后，我们证明了这类上图模式语言是多项式时间归纳推理的正数据。
A cograph (complement reducible graph) is a graph which can be generated by disjoint union and complement operations on graphs, starting with a single vertex graph. Cographs arise in many areas of computer science and are studied extensively.With the goal of developing an effective data mining method for graph structured data, in this paper we introduce a graph pattern expression, called acograph pattern, which is a special type of cograph having structured variables. Firstly, we present a polynomial time matching algorithm for cograph patterns. Secondly, we give a polynomial time algorithm for obtaining a minimally generalized cograph pattern which explains given positive data. Finally, we show that the class of cograph pattern languages is polynomial time inductively inferable from positive data.