Polynomial Time Inductive Inference of Languages of Ordered Term Tree Patterns with Height-Constrained Variables from Positive Data

Access this Article

Author(s)

Abstract

<p>An efficient means of learning tree-structural features from tree-structured data would enable us to construct effective mining methods for tree-structured data. Here, a pattern representing rich tree-structural features common to tree-structured data and a polynomial time algorithm for learning important tree patterns are necessary for mining knowledge from tree-structured 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 height-constrained variable. A height-constrained 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 height-constrained replacement. A sequence of consecutive height-constrained variables is called a variable-chain. In this paper, we present polynomial time algorithms for solving the membership problem and the minimal language (MINL) problem for term tree patternshaving no variable-chain. 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 height-constrained replacements to all height-constrained 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 tree-structured data. Finally, we show that the class, i.e., the set of all term tree patternshaving no variable-chain, 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), 785-802, 2017

    The Institute of Electronics, Information and Communication Engineers

Codes

Page Top