Two related algorithms for root-to-frontier tree pattern matching

L.G.W.A. Cleophas, C. Hemerik, G. Zwaan

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)
    4 Downloads (Pure)


    Tree pattern matching (TPM) algorithms on ordered, ranked trees play an important role in applications such as compilers and term rewriting systems. Many TPM algorithms appearing in the literature are based on tree automata. For efficiency, these automata should be deterministic, yet deterministic root-to-frontier tree automata (DRFTAS) are less powerful than nondeterministic ones, and no root-to-frontier TPM algorithm using a DRFTA has appeared so far. Hoffmann & O'Donnell presented a root-to-frontier TPM algorithm based on an Aho-Corasick automaton recognizing tree stringpaths. No relationship between this algorithm and algorithms using tree automata has however been described. We show that a specific DRFTA can be used for stringpath matching in a root-to-frontier TPM algorithm. This new algorithm provides a missing link between TPM algorithms using stringpath automata and those using tree automata. We also investigate the correspondence between the automata used by the two algorithms.
    Original languageEnglish
    Pages (from-to)1253-1272
    JournalInternational Journal of Foundations of Computer Science
    Issue number6
    Publication statusPublished - 2006


    Dive into the research topics of 'Two related algorithms for root-to-frontier tree pattern matching'. Together they form a unique fingerprint.

    Cite this