@inproceedings{3c8b46634cc04af2bd0fc58adc40f94d,
title = "Some Complexity Theoretic Aspects of AC Rewriting",
abstract = "In this paper we establish several tight complexity bounds on the sequential and parallel complexity of the associative-commutative (AC) matching problem and its variants. One of our main contributions in this paper is the demonstration of a much tighter relationship between AC matching of linear terms and bipartite matching in both sequential and parallel computation. Another contribution is the use of complexity theoretic techniques to find parallelism in these problems. We believe that this approach can be successfully applied to other matching and unification problems that are not amenable to direct parallelization.",
keywords = "Bipartite Match, Function Symbol, Parallel Complexity, Proof Sketch, Turing Machine",
author = "Verma, \{Rakesh M.\} and Ramakrishnan, \{I. V.\}",
note = "Publisher Copyright: {\textcopyright} 1989 Springer-Verlag Berlin Heidelberg.; 6th Symposium on Theoretical Aspects of Computer Science, STACS 1989 ; Conference date: 16-02-1989 Through 18-02-1989",
year = "1989",
doi = "10.1007/BFb0029003",
language = "English",
isbn = "9783540508403",
series = "Lecture Notes in Computer Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "407--420",
editor = "Burkhard Monien and Robert Cori",
booktitle = "STACS 89 - 6th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
}