Tight complexity bounds for term matching problems

AbstractIn this paper we study the sequential and parallel complexity of various important term matching problems. These problems occur frequently in applications such as term rewriting, functional programming, and logic programming. First, we obtain non-trivial lower bounds on the parallel complexity of the (uninterpreted) term matching problem. We also establish the tightness of these bounds for some representations and several models. We then characterize completely the sequential complexity of associative and commutative matching when the number of occurrences of variables is varied. Specifically, we show that even if each variable is restricted to at most two occurrences in the terms, both associative matching and commutative matching are NP-complete. Interestingly, for the important restriction of boolean terms we show that commutative matching is NP-complete whereas associative matching has a linear time sequential algorithm. For linear terms, we significantly improve the existing upper bound for associative-commutative matching, and present a new algorithm for associative matching. Designing direct parallel algorithms for associative-commutative matching of linear terms appears to be a difficult task. Despite this we have been able to resolve questions about the parallel complexity of these problems using complexity-theoretic techniques. Finally, an interesting consequence of the research reported here is the demonstration of a tighter relationship between associative-commutative matching for linear terms and bipartite matching on both sequential and parallel models