Tight complexity bounds for term matching problems (Q1201724)

Matching is an important operation in symbolic computations (e.g. rewriting, subsumption test), so some research has been done to design efficient algorithms and to study the complexity of the problem. The present paper is concerned with two problems: parallel complexity if all operators are uninterpreted and sequential and parallel complexity if some operators are commutative and/or associative. For studying the parallel complexity of the matching problem several variants of the PRAM (parallel random access machine) are considered, the differences are concurrent versus exclusive read and write operations. Furthermore, different data structures for the terms are considered: linear strings stored in arrays, trees and directed acyclic graphs. A lower bound of \(\Omega(\log n/\log\log n)\) for the CRCW PRAM and \(\Omega(\log n)\) for the CREW PRAM are derived (independent of the data structure), even if the terms are restricted to be linear. These bounds are proved to be tight by presenting algorithms with these time bounds working also for nonlinear problems. For interpreted operations the problems associative (AM), commutative (CM) and associative-commutative matching (ACM) are studied, together with their restrictions to linear problems (CML, AML, ACML) and to Boolean terms (no argument of an AC-symbol is a variable). For the sequential complexity, results of \textit{D. Benanav}, \textit{D. Kapur} and \textit{p. Narendran} [Lect. Notes Comput. Sci. 202, 417-429 (1985; Zbl 0576.68038)] are improved, e.g. \(O(| s|\cdot| t|^{1.5})\) instead of \(O(| s|\cdot| t|^ 3)\) as lower time bound for ACML is derived, and already 2-occurrence ACM is NP-complete compared to 3-occurrence ACM in Benanav et al. For the parallel complexity of linear matching problems some connections to well-known problems are established, to bipartite matching and to rooted subtree isomorphism. Here are some results: AML and CML are in NL (log-space acceptable on a non-terministic Turing machine) and hence in \(NC^ 2\) (using a result of Borodin). Restricted \(\text{ACML}\equiv_{NC}\) subtree isomorphism \(\equiv_{NC}\) bipartite matching.