The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Istilah ialah corak graf akiklik yang disambungkan (pokok tidak tertib tidak berakar) dengan pembolehubah berstruktur, yang merupakan senarai tertib satu atau lebih bucu yang berbeza. Pembolehubah istilah mempunyai label pembolehubah dan boleh digantikan dengan pokok arbitrari dengan penggantian hyperedge mengikut label pembolehubah. Dimensi sebutan ialah bilangan maksimum bucu dalam pembolehubahnya. Sebutan dikatakan linear jika setiap label pembolehubah di dalamnya berlaku tepat sekali. biarlah T menjadi pokok dan t istilah linear. Dalam kertas kerja ini, kami mengkaji masalah padanan corak graf (GPMP) untuk T and t, yang menentukan sama ada atau tidak T diperoleh daripada t dengan menggantikan pembolehubah dalam t dengan beberapa pokok. Mula-mula kita tunjukkan bahawa GPMP untuk T and t adalah NP-lengkap jika dimensi bagi t adalah lebih besar daripada atau sama dengan 4. Seterusnya kami memberikan algoritma masa polinomial untuk menyelesaikan GPMP bagi pepohon darjah sempadan dan sebutan linear dimensi sempadan. Akhir sekali kami menunjukkan bahawa GPMP untuk pokok darjah arbitrari dan sebutan linear dimensi 2 boleh diselesaikan dalam masa polinomial.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -