Tight complexity bounds for term matching problems
type: Item
instance of: scholarly article
title: Tight complexity bounds for term matching problems
zbMATH Open document ID: 0759.68040
DOI: 10.1016/0890-5401(92)90075-Q
author: Rakesh M. Verma
author: I. V. Ramakrishnan
published in: Information and Computation
publication date: 1993-01-17T00:00:00Z
review text: 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…
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 98385
reviewed by: Jürgen Avenhaus
MaRDI profile type: Publication
cites work: Complexity of matching problems
cites work: On Relating Time and Space to Size and Depth
cites work: A taxonomy of problems with fast parallel algorithms
cites work: On the sequential nature of unification
cites work: Parallel Algorithms for Term Matching
cites work: Parallelism in random access machines
cites work: Q4198056
cites work: Subtree isomorphism is NC reducible to bipartite perfect matching
cites work: Matching is as easy as matrix inversion
cites work: Q3776590
cites work: Linear unification
cites work: Q3779742
cites work: Automata-driven indexing of prolog clauses
cites work: Term matching on parallel computers
cites work: An Analysis of a Good Algorithm for the Subtree Problem
cites work: Finding the maximum, merging, and sorting in a parallel computation model
cites work: Simulation of Parallel Random Access Machines by Circuits
cites work: An Efficient Parallel Biconnectivity Algorithm
cites work: Q3761692
cites work: An Analysis of a Good Algorithm for the Subtree Problem, Corrected
description: scientific article; zbMATH DE number 98385