Tree pattern matching from regular tree expressions

Ahlem Belabbaci, Hadda Cherroun, Loek Cleophas, Djelloul Ziadi

    Research output: Contribution to journalArticleAcademicpeer-review

    879 Downloads (Pure)


    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
    Issue number2
    Publication statusPublished - 1 Jan 2018


    • Regular tree expressions
    • Thompson Tree automata
    • Tree automata
    • Tree pattern matching


    Dive into the research topics of 'Tree pattern matching from regular tree expressions'. Together they form a unique fingerprint.

    Cite this