@inproceedings{3fd86713a9b54847924dfd6ebc42496d,
title = "Optimal speedups for parallel pattern matching in trees",
abstract = "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. If n and m are the number of nodes in the subject and pattern tree respectively and if no restriction is placed on the structure of the trees, then the fastest known sequential algorithm for linear tree pattern matching requires O(nm) time in the worst case. In this paper we present a parallel algorithm for linear tree pattern matching on a PRAM (parallel random access machine) model. Our algorithm exhibits optimal speedup, in the sense that its processor-time product matches the worst-case time complexity of the fastest sequential algorithm.",
author = "R. Ramesh and Ramakrishnan, \{I. V.\}",
note = "Publisher Copyright: {\textcopyright} 1987, Springer-Verlag.; 2nd International Conference on Rewriting Techniques and Applications, RTA 1987 ; Conference date: 25-05-1987 Through 27-05-1987",
year = "1987",
doi = "10.1007/3-540-17220-3\_23",
language = "English",
isbn = "9783540172208",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "274--285",
editor = "Pierre Lescanne",
booktitle = "Rewriting Techniques and Applications, Proceedings",
}