@inproceedings{5bc07b7373704841bcc8afc4b8d55d2d,
title = "Distributed algorithms for tree pattern matching",
abstract = "We present efficient distributed algorithms for the Tree Pattern Matching problem. To the best of our knowledge, these are the first distributed algorithms of this nature. Tree pattern matciffng is a fundamental operation in many programming task such as code optimization and automated theorem proving, and has a number of applications in distributed systems. We present both a top-down and bottom-up algorithm for linear tree pattern matching (where any variable occurs at most once in the pattern) for the case in which tile subject tree is completely distributed as a node per processor. Tile pattern is assumed to reside within the local memory of each processor. Let the subject tree have n nodes and height hs, and the pattern m nodes and height hp. The top-down algorithm has bit complexity O(n log m hp) and time complexity O(hs), while the bottom-up algorithm has bit complexity O(n hp) and time complexity O(hp). However, the bottom-up algorithm requires preprocessing of the subject and pattern trees. An efficient extension of these distributed algorithms to the case of multiple patterns is also given.",
author = "Gurdip Singh and Smolka, {Scott A.} and Ramakrishnan, {I. V.}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1988.; 2nd International Workshop on Distributed Algorithms, WDAG 1987 ; Conference date: 08-07-1987 Through 10-07-1987",
year = "1988",
doi = "10.1007/BFb0019797",
language = "English (US)",
isbn = "9783540193661",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "92--107",
editor = "{van Leeuwen}, J.",
booktitle = "Distributed Algorithms - 2nd International Workshop, Proceedings",
}