Polynomial Time Inductive Inference of Languages of Ordered Term Tree Patterns with HeightConstrained Variables from Positive Data
Access this Article
Author(s)
Abstract
<p>An efficient means of learning treestructural features from treestructured data would enable us to construct effective mining methods for treestructured data. Here, a pattern representing rich treestructural features common to treestructured data and a polynomial time algorithm for learning important tree patterns are necessary for mining knowledge from treestructured data. As such a tree pattern, we introduce a term tree pattern <i>t</i> such that any edge label of <i>t</i> belongs to a finite alphabet Λ, any internal vertex of <i>t</i> has ordered children and <i>t</i> has a new kind of structured variable, called a heightconstrained variable. A heightconstrained variable has a pair of integers (<i>i</i>, <i>j</i>) as constraints, and it can be replaced with a tree whose trunk length is at least <i>i</i> and whose height is at most <i>j</i>. This replacement is called heightconstrained replacement. A sequence of consecutive heightconstrained variables is called a variablechain. In this paper, we present polynomial time algorithms for solving the membership problem and the minimal language (MINL) problem for term tree patternshaving no variablechain. The membership problem for term tree patternsis to decide whether or not a given tree can be obtained from a given term tree pattern by applying heightconstrained replacements to all heightconstrained variables in the term tree pattern. The MINL problem for term tree patternsis to find a term tree pattern <i>t</i> such that the language generated by <i>t</i> is minimal among languages, generated by term tree patterns, which contain all given treestructured data. Finally, we show that the class, i.e., the set of all term tree patternshaving no variablechain, is polynomial time inductively inferable from positive data if Λ ≥ 2.</p>
Journal

 IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100.A(3), 785802, 2017
The Institute of Electronics, Information and Communication Engineers