Geodesic
Tree pattern matching from regular tree expressions
Kybernetika, Tome 54 (2018) no. 2, pp. 221-242

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

In this work we deal with tree pattern matching over ranked trees, where the pattern set to be matched against is defined by a regular tree expression. We present a new method that uses a tree automaton constructed inductively from a regular tree expression. First we construct a special tree automaton for the regular tree expression of the pattern $E$, which is somehow a generalization of Thompson automaton for strings. Then we run the constructed automaton on the subject tree $t$. The pattern matching algorithm requires an $\mathcal{O}(\vert t\vert\vert E\vert)$ time complexity, where $\vert t\vert$ is the number of nodes of $t$ and $\vert E\vert$ is the size of the regular tree expression $E$. The novelty of this contribution besides the low time complexity is that the set of patterns can be infinite, since we use regular tree expressions to represent patterns.
DOI : 10.14736/kyb-2018-2-0221
Classification : 68Q45
Keywords: tree automata; Thompson Tree automata; regular tree expressions; tree pattern matching 
@article{10_14736_kyb_2018_2_0221,
     author = {Belabbaci, Ahlem and Cherroun, Hadda and Cleophas, Loek and Ziadi, Djelloul},
     title = {Tree pattern matching from regular tree expressions},
     journal = {Kybernetika},
     pages = {221--242},
     publisher = {mathdoc},
     volume = {54},
     number = {2},
     year = {2018},
     doi = {10.14736/kyb-2018-2-0221},
     mrnumber = {3807712},
     zbl = {06890417},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-2-0221/}
}
TY  - JOUR
AU  - Belabbaci, Ahlem
AU  - Cherroun, Hadda
AU  - Cleophas, Loek
AU  - Ziadi, Djelloul
TI  - Tree pattern matching from regular tree expressions
JO  - Kybernetika
PY  - 2018
SP  - 221
EP  - 242
VL  - 54
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-2-0221/
DO  - 10.14736/kyb-2018-2-0221
LA  - en
ID  - 10_14736_kyb_2018_2_0221
ER  - 
%0 Journal Article
%A Belabbaci, Ahlem
%A Cherroun, Hadda
%A Cleophas, Loek
%A Ziadi, Djelloul
%T Tree pattern matching from regular tree expressions
%J Kybernetika
%D 2018
%P 221-242
%V 54
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-2-0221/
%R 10.14736/kyb-2018-2-0221
%G en
%F 10_14736_kyb_2018_2_0221
Belabbaci, Ahlem; Cherroun, Hadda; Cleophas, Loek; Ziadi, Djelloul. Tree pattern matching from regular tree expressions. Kybernetika, Tome 54 (2018) no. 2, pp. 221-242. doi: 10.14736/kyb-2018-2-0221

Cité par Sources :