@inproceedings{bd6ad14c2a6e445b9eecd4d2a8b16294,
title = "An efficient parallel algorithm for term matching",
abstract = "Term matching is a compute-intensive problem that often arises in symbolic manipulation systems like term rewriting, and in functional and equational programming. A parallel algorithm for term matching on the CREW PRAM model was recently described by Dwork, Kanellakis and Stockmeyer. This algorithm requires O(n2) processors and takes either O(logn) or O(log2n) time. In this paper we describe a new parallel algorithm that performs term matching in O(log2n) time using O(n) processors. In our algorithm, we represent the two terms as labeled directed trees. We then construct equivalence classes of nodes in these two trees such that two nodes are in the same class iff they have the same sequence of edge-labels on the path to their respective roots. This is the basis of our parallel algorithm for term matching.",
author = "Verma, \{Rakesh M.\} and T. Krishnaprasad and Ramakrishnan, \{I. V.\}",
note = "Publisher Copyright: {\textcopyright} 1986, Springer Verlag. All rights reserved.; 6th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1986 ; Conference date: 18-12-1986 Through 20-12-1986",
year = "1986",
doi = "10.1007/3-540-17179-7\_31",
language = "English",
isbn = "9783540171799",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "504--518",
editor = "Nori, \{Kesav V.\}",
booktitle = "Foundations of Software Technology and Theoretical Computer Science - 6th Conference, Proceeding",
}