
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Polynomial Time Inductive Inference of Languages of Ordered Term Tree Patterns with HeightConstrained Variables from Positive Data
Takayoshi SHOUDAI Kazuhide AIKOH Yusuke SUZUKI Satoshi MATSUMOTO Tetsuhiro MIYAHARA Tomoyuki UCHIDA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E100A
No.3
pp.785802 Publication Date: 2017/03/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E100.A.785
Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: tree structured pattern, heightconstrained variable, polynomial time algorithm, inductive inference, computational learning theory,
Full Text: PDF(2.3MB)>>
Summary:
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 t such that any edge label of t belongs to a finite alphabet Λ, any internal vertex of t has ordered children and t has a new kind of structured variable, called a heightconstrained variable. A heightconstrained variable has a pair of integers (i, j) as constraints, and it can be replaced with a tree whose trunk length is at least i and whose height is at most j. 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 t such that the language generated by t 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.

