@inproceedings{533943a5524440489a4840f98ef60aba,
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",
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",
}