𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parallel tree pattern matching

✍ Scribed by R. Ramesh; I.V. Ramakrishnan

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
819 KB
Volume
9
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

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 of any variable in the pattern occurs at most once. In this paper we describe a new parallel algorithm for linear tree pattern matching using a parallel random access machine model.

πŸ“œ SIMILAR VOLUMES

A parallel algorithm for tree pattern ma
A parallel algorithm for tree pattern matching
✍ Koji Tarora; Tomio Hirata; Yasuyoshi Inagaki πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 814 KB

## 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__ proc

Simple Optimal Parallel Multiple Pattern
Simple Optimal Parallel Multiple Pattern Matching
✍ S Muthukrishnan πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 96 KB

In this paper, we present a simple algorithm for solving the multipattern matching problem, with optimal speedup. The best-known deterministic parallel algorithm for this problem also provides optimal speedup, but relies crucially on a sophisticated construction of an automaton. Since then, Rabin ha

Parallel computation of matchings in tre
Parallel computation of matchings in trees
✍ Constantine N.K. Osiakwan; Selim G. Akl πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 932 KB

We present adaptive parallel algorithms for b-matchings in trees. The algorithms are designed using the exclusive-read exclusive-write parallel random-access machine (EREW PRAM) model of parallel computation. For a tree of n vertices, we present an algorithm that determines a maximum cardinality b-m

Pattern matching in trees and nets
Pattern matching in trees and nets
✍ Hans-Ulrich Simon πŸ“‚ Article πŸ“… 1983 πŸ› Springer-Verlag 🌐 English βš– 766 KB
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