Hard Optimization Problems in Learning Tree Contraction Patterns, Applied Computing and Information Technology
Hard Optimization Problems in Learning Tree Contraction Patterns, Applied Computing and Information Technology
复制标题
学习树收缩模式、应用计算和信息技术中的硬优化问题
DOI：
10.1007/978-3-319-05717-0_6
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Y. Okamoto and T . Shoudai
中科院分区：
文献类型：
--
作者：
内山 祥吾;大林 正直;呉本 尭;小林 邦和;間普 真吾;Y. Okamoto and T . Shoudai
树收缩模式(TC模式)是给定的无序树所共有的无序树结构模式，它是通过边收缩将每个不常见的连通子结构合并成一个顶点而得到的。为了从树结构的文档中提取有意义的和隐藏的知识，我们考虑了TC模式的最小语言问题。TC-模式的MINL问题是找到一个TC-模式，使得由生成的语言是由TC-模式生成的语言中的最小语言，该TC-模式包含所有给定的无序树。最近，文献[8]证明了如果有无穷多个顶点标号，TC-模式的MINL问题在多项式时间内是可计算的。在本章中，我们讨论了MINL问题的两个优化版本，它们被称为具有树大小最大化的MINL(Max MINL)和具有可变大小最小化的MINL(Min-Max MINL)。我们证明了MAX MINLI是NP完全的，MIN-MAX MINLI是MAX SNP-HARD的。
Atree contraction pattern(TC-pattern) is an unordered tree-structured pattern common to given unordered trees, which is obtained by merging every uncommon connected substructure into one vertex by edge contraction. In order to extract meaningful and hidden knowledge from tree structured documents, we consider a minimal language (MINL) problem for TC-patterns . The MINL problem for TC-patterns is to find a TC-patternsuch that the language generated byis minimal among languages, generated by TC-patterns, which contain all given unordered trees. Recently, [8] showed that the MINL problem for TC-patterns is computable in polynomial time if there are infinitely many vertex labels. In this chapter, we discuss two optimization versions of the MINL problem, which are calledMINL with Tree-size Maximization (MAX MINL)andMINL with Variable-size Minimization (MIN-MAX MINL). We show thatMAX MINLis NP-complete andMIN-MAX MINLis MAX SNP-hard.