检索结果-内蒙古大学图书馆

An Efficient pattern matching algorithm for Unordered Term Tree patterns of Bounded Dimension

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2018年第9期E101A卷 1344-1354页

作者： Shoudai, Takayoshi Miyahara, Tetsuhiro Uchida, Tomoyuki Matsumoto, Satoshi Suzuki, Yusuke Kyushu Int Univ Fac Contemporary Business Kitakyushu Fukuoka 8058512 Japan Hiroshima City Univ Fac Informat Sci Hiroshima 7313194 Japan Tokai Univ Fac Sci Hiratsuka Kanagawa 2591292 Japan

A term tree pattern is a connected acyclic graph (unrooted unordered tree) pattern with structured variables, which are ordered lists of one or more distinct vertices. A variable of a termtree pattern has a variable label and can be replaced with an arbitrary tree by hyperedge replacement according to the variable label. The dimension of a term tree pattern is the maximum number of vertices in the variables of it. A term tree pattern is said to be linear if each variable label in it occurs exactly once. Let T be a tree and t a linear termtree pattern. In this paper, we study the graph pattern matching problem (GPMP) for T and t, which decides whether or not T is obtained from t by replacing variables in t with some trees. First we show that GPMP for T and t is NP-complete if the dimension of t is greater than or equal to 4. Next we give a polynomial time algorithm for solving GPMP for a tree of bounded degree and a linear term tree pattern of bounded dimension. Finally we show that GPMP for a tree of arbitrary degree and a linear term tree pattern of dimension 2 is solvable in polynomial time.

关键词： tree structured pattern graph pattern matching algorithm polynomial time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

An Efficient pattern matching algorithm for Ordered Term Tree patterns

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2015年第6期E98A卷 1197-1211页

作者： Suzuki, Yusuke Shoudai, Takayoshi Uchida, Tomoyuki Miyahara, Tetsuhiro Hiroshima City Univ Grad Sch Informat Sci Hiroshima 7313194 Japan Kyushu Int Univ Fac Int Studies Kitakyushu Fukuoka 8058512 Japan

A term tree pattern is a rooted ordered tree pattern which consists of ordered tree structures with edge labels and structured variables with labels. All variables with the same label in a term tree pattern can be simultaneously replaced with ordered trees isomorphic to the same rooted ordered tree. Then, a term tree pattern is suitable for representing structural features common to tree structured data such as XML documents on the web, the secondary structures of RNA in biology and parse trees describing grammatical structures of natural languages. Let OTT be the set of all term tree patterns which have one or more variables with the same label. Let LOTT be the set of all term tree patterns t such that all variables in t have distinct labels. We remark that LOTT subset of OTT holds. In this paper, we consider a problem, called matching problem for term tree patterns, of deciding whether or not a given rooted ordered tree T is obtained from a given term tree pattern t by replacing variables in t with rooted ordered trees. We show that matching problem for term tree patterns in OTT is NP-complete, by giving a reduction from the string pattern matching problem, which is NP-complete. Next, by giving operations on an interval, which is a set containing all integers between two given integers representing vertex identifiers, we propose an efficient algorithm for solving matching problem for term tree patterns in LOTT. Then, we show that, when an ordered tree having N vertices and a term tree pattern t. LOTT having n vertices are given, the proposed matching algorithm correctly solves this problem in O(nN) time.

关键词： ordered tree structured pattern graph pattern matching algorithm polynomial time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：