The search functionality is under construction.

The search functionality is under construction.

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 *T* be a tree and *t* a linear term. In this paper, we study the graph pattern matching problem (GPMP) for *T* and *t*, which decides whether or not *T* is obtained from *t* by replacing variables in *t* with some trees. First we show that GPMP for *T* and *t* is NP-complete if the dimension of *t* 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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1344-1354

- Publication Date
- 2018/09/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E101.A.1344

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

Takayoshi SHOUDAI

Kyushu International University

Tetsuhiro MIYAHARA

Hiroshima City University

Tomoyuki UCHIDA

Hiroshima City University

Satoshi MATSUMOTO

Tokai University

Yusuke SUZUKI

Hiroshima City University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Takayoshi SHOUDAI, Tetsuhiro MIYAHARA, Tomoyuki UCHIDA, Satoshi MATSUMOTO, Yusuke SUZUKI, "An Efficient Pattern Matching Algorithm for Unordered Term Tree Patterns of Bounded Dimension" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1344-1354, September 2018, doi: 10.1587/transfun.E101.A.1344.

Abstract: 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 *T* be a tree and *t* a linear term. In this paper, we study the graph pattern matching problem (GPMP) for *T* and *t*, which decides whether or not *T* is obtained from *t* by replacing variables in *t* with some trees. First we show that GPMP for *T* and *t* is NP-complete if the dimension of *t* 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1344/_p

Copy

@ARTICLE{e101-a_9_1344,

author={Takayoshi SHOUDAI, Tetsuhiro MIYAHARA, Tomoyuki UCHIDA, Satoshi MATSUMOTO, Yusuke SUZUKI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={An Efficient Pattern Matching Algorithm for Unordered Term Tree Patterns of Bounded Dimension},

year={2018},

volume={E101-A},

number={9},

pages={1344-1354},

abstract={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 *T* be a tree and *t* a linear term. In this paper, we study the graph pattern matching problem (GPMP) for *T* and *t*, which decides whether or not *T* is obtained from *t* by replacing variables in *t* with some trees. First we show that GPMP for *T* and *t* is NP-complete if the dimension of *t* 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.},

keywords={},

doi={10.1587/transfun.E101.A.1344},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1344

EP - 1354

AU - Takayoshi SHOUDAI

AU - Tetsuhiro MIYAHARA

AU - Tomoyuki UCHIDA

AU - Satoshi MATSUMOTO

AU - Yusuke SUZUKI

PY - 2018

DO - 10.1587/transfun.E101.A.1344

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E101-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2018

AB - 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 *T* be a tree and *t* a linear term. In this paper, we study the graph pattern matching problem (GPMP) for *T* and *t*, which decides whether or not *T* is obtained from *t* by replacing variables in *t* with some trees. First we show that GPMP for *T* and *t* is NP-complete if the dimension of *t* 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.

ER -