Tree pattern matching from regular tree expressions

Ahlem Belabbaci, Hadda Cherroun, Loek Cleophas, Djelloul Ziadi

Research output: Contribution to journalArticleAcademicpeer-review

322 Downloads (Pure)

Abstract

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 O(|t||E|) time complexity, where |t| is the number of nodes of t and |E| 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.
Original languageEnglish
Pages (from-to)221-242
Number of pages22
JournalKybernetika
Volume54
Issue number2
DOIs
Publication statusPublished - 2018

Fingerprint

Pattern matching
Pattern Matching
Tree Automata
Time Complexity
Automata
Matching Algorithm
Low Complexity
Strings
Vertex of a graph

Cite this

Belabbaci, Ahlem ; Cherroun, Hadda ; Cleophas, Loek ; Ziadi, Djelloul. / Tree pattern matching from regular tree expressions. In: Kybernetika. 2018 ; Vol. 54, No. 2. pp. 221-242.
@article{aad22e8298134ef4b1a6eb25aff3f992,
title = "Tree pattern matching from regular tree expressions",
abstract = "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 O(|t||E|) time complexity, where |t| is the number of nodes of t and |E| 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.",
author = "Ahlem Belabbaci and Hadda Cherroun and Loek Cleophas and Djelloul Ziadi",
year = "2018",
doi = "10.14736/kyb-2018-2-0221",
language = "English",
volume = "54",
pages = "221--242",
journal = "Kybernetika",
issn = "0023-5954",
publisher = "Academy of Sciences of the Czech Republic",
number = "2",

}

Belabbaci, A, Cherroun, H, Cleophas, L & Ziadi, D 2018, 'Tree pattern matching from regular tree expressions', Kybernetika, vol. 54, no. 2, pp. 221-242. https://doi.org/10.14736/kyb-2018-2-0221

Tree pattern matching from regular tree expressions. / Belabbaci, Ahlem; Cherroun, Hadda; Cleophas, Loek; Ziadi, Djelloul.

In: Kybernetika, Vol. 54, No. 2, 2018, p. 221-242.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Tree pattern matching from regular tree expressions

AU - Belabbaci, Ahlem

AU - Cherroun, Hadda

AU - Cleophas, Loek

AU - Ziadi, Djelloul

PY - 2018

Y1 - 2018

N2 - 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 O(|t||E|) time complexity, where |t| is the number of nodes of t and |E| 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.

AB - 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 O(|t||E|) time complexity, where |t| is the number of nodes of t and |E| 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.

U2 - 10.14736/kyb-2018-2-0221

DO - 10.14736/kyb-2018-2-0221

M3 - Article

VL - 54

SP - 221

EP - 242

JO - Kybernetika

JF - Kybernetika

SN - 0023-5954

IS - 2

ER -