@inproceedings{a961cbac03764fbea05a94e090c6d64b,
title = "Optimal time bounds for parallel term matching",
abstract = "Term Matching is a fundamental operation in term rewriting, functional programming and logic programming. Parallel algorithms for this operation have attracted much attention recently. However nontrivial lower bounds for term matching are as yet unknown. In this paper, we obtain lower bounds on parallel time for this problem. We also establish the tightness of our lower bounds for some representations and several models, by giving matching upper bounds with as few processors as possible.",
keywords = "Complexity, Optimal bounds, Parallel term matching",
author = "Verma, \{Rakesh M.\} and Ramakrishnan, \{I. V.\}",
note = "Publisher Copyright: {\textcopyright} 1988, Springer-Verlag.; 9th International Conference on Automated Deduction, CADE 1988 ; Conference date: 23-05-1988 Through 26-05-1988",
year = "1988",
doi = "10.1007/BFb0012867",
language = "English",
isbn = "9783540193432",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "694--703",
editor = "Ewing Lusk and Ross Overbeek",
booktitle = "9th International Conference on Automated Deduction, Proceedings",
}