Tight complexity bounds for term matching problems

DOI10.1016/0890-5401(92)90075-QMaRDI QIDQ1201724zbMATH OpenFDO

Authors Rakesh M. Verma, I. V. Ramakrishnan

Publication date 17 January 1993

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(92)90075-Q

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

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.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Tight complexity bounds for term matching problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201724)