𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A parallel algorithm for tree pattern matching

✍ Scribed by Koji Tarora; Tomio Hirata; Yasuyoshi Inagaki

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
814 KB
Volume
24
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Given a text tree t and a pattern tree p, tree pattern matching involves finding subtrees of t which match p. This paper proposed a parallel algorithm for tree pattern matching. The algorithm is designed to run in O(log n) parallel time using mn/log__n__ processors on CREW‐PRAM, where n and m are the sizes of t and p respectively. This improves the result of Ramesh et al. that runs in O(log^2^n) time using nr/log^2^n processors, where r is the number of vertices of p labeled with variables. Futhermore, the method of processor allocation is described specifically in the proposed algorithm.

πŸ“œ SIMILAR VOLUMES

Parallel tree pattern matching
Parallel tree pattern matching
✍ R. Ramesh; I.V. Ramakrishnan πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 819 KB

Tree pattern matching is a fundamental operation that is used in a number of programming tasks such as code optimization in compilers, symbolic computation, automatic theorem proving and term rewriting. An important special case of this operation is linear tree pattern matching in which an instance

A new algorithm for linear regular tree
A new algorithm for linear regular tree pattern matching
✍ Priti Shankar; Amitranjan Gantait; A.R. Yuvaraj; Maya Madhavan πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 129 KB

We consider the problem of linear regular tree pattern matching and describe a new solution based on a bottom up technique. Current bottom up techniques preprocess the patterns and construct a ΓΏnite state tree pattern matching automaton for the purpose. Though matching time is linear in the size of