An Efficient Pattern Matching Algorithm for Ordered Term Tree Patterns with Contractible Variables

A term tree pattern is a rooted ordered tree pattern which consists of ordered tree structures with edge labels and structured variables with labels. A variable in a term tree pattern is a labeled hyperedge which can be replaced with any ordered tree that has at least 2 vertices. In this paper, we focus on a special type of variable, called a contractible variable. A contractible variable can be replaced with any ordered tree that has at least 1 vertex. A usual variable, called an uncontractible variable, cannot be replaced with an ordered tree that consists of a single vertex. The matching problem for term tree patterns is to decide whether or not a given ordered tree can be obtained from a given term tree pattern by replacing variables in the term tree pattern with ordered trees. Previously, we proposed a polynomial time matching algorithm for solving the matching problem for termtree patterns having uncontractible variables. In this paper, we propose a matching algorithm for solving the matching problem for termtree patterns having contractible variables and uncontractible variables. Furthermore, we show that the proposed algorithm correctly solves this problem in O(n4N) time, where n and N denote the numbers of vertices of a given term tree pattern and a given ordered tree, respectively.