An Efficient Pattern Matching Algorithm for Unordered Term Tree Patterns of Bounded Dimension

Access this Article

Author(s)

Abstract

<p>A term 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 term 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 is the maximum number of vertices in the variables of it. A term is said to be linear if each variable label in it occurs exactly once. Let <i>T</i> be a tree and <i>t</i> a linear term. In this paper, we study the graph pattern matching problem (GPMP) for <i>T</i> and <i>t</i>, which decides whether or not <i>T</i> is obtained from <i>t</i> by replacing variables in <i>t</i> with some trees. First we show that GPMP for <i>T</i> and <i>t</i> is NP-complete if the dimension of <i>t</i> 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 of bounded dimension. Finally we show that GPMP for a tree of arbitrary degree and a linear term of dimension 2 is solvable in polynomial time.</p>

Journal

  • IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E101.A(9), 1344-1354, 2018

    The Institute of Electronics, Information and Communication Engineers

Codes

Page Top