✦ LIBER ✦

Algorithms and reductions for rewriting problems. II

✍ Scribed by Rakesh Verma

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 86 KB
Volume: 84
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(02)00395-2

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we give polynomial-time reductions between a version of joinability for rewrite systems and the word problem for rewrite systems. We prove log-space hardness or completeness for P for several problems of ground rewrite systems. We show that matching (and unification) modulo ground equations is NP-hard even when variables are restricted to at most two occurrences in the pattern and the subject is just a constant. Finally, we give the first polynomial-time algorithms for matching modulo ground equations with linear pattern and for joinability problem with ground rewrite systems. The joinability result leads to polynomial time algorithms for: local confluence of ground rewrite systems, confluence of terminating ground rewrite systems, and completeness of ground rewrite systems. The results for matching modulo ground equations are optimal with respect to occurrences of variables.

📜 SIMILAR VOLUMES

A reduction algorithm for sublinear Diri

A reduction algorithm for sublinear Dirichlet problems

✍ Jorge Cossio; Sheldon Lee; John M. Neuberger 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 454 KB

We consider a sublinear elliptic BVP on the unit square and recall proofs for the existence of five solutions. Previous algorithms which follow the constructive nature of the existence proofs are able to find four of these solutions. The fifth solution follows from an application of the Lyapunov-Sch

Residual reduction algorithms for nonsym

Residual reduction algorithms for nonsymmetric saddle point problems

✍ Constantin Bacuta; Brendan McCracken; Lu Shu 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 559 KB

In this paper, we introduce and analyze Uzawa algorithms for non-symmetric saddle point systems. Convergence for the algorithms is established based on new spectral results about Schur complements. A new Uzawa type algorithm with optimal relaxation parameters at each new iteration is introduced and

Decomposition Plans for Geometric Constr

Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms

✍ Christoph M. Hoffman; Andrew Lomonosov; Meera Sitharam 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 409 KB

We systematically design two new decomposition-recombination (DR) planners, geared to perform well with respect to several performance measures. The DR-planning problem and the performance measures were formally defined in Part I of this paper to closely reflect specific requirements of CAD/CAM appl

Rational Krylov algorithms for nonsymmet

Rational Krylov algorithms for nonsymmetric eigenvalue problems. II. matrix pairs

✍ Axel Ruhe 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 613 KB

Term Rewriting for the Conjugacy Problem

Term Rewriting for the Conjugacy Problem and the Braid Groups

✍ John Pedersen; Margaret Yoder 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 312 KB

Parallel Algorithms for Orthotropic Prob

Parallel Algorithms for Orthotropic Problems

✍ Ivar Gustafsson; Gunhild Lindskog 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 784 KB

Finite element meshes and node-numberings suitable for parallel solution with equally loaded processors are presented for linear orthotropic elliptic partial differential equations. These problems are of great importance, for instance in the oil and airfoil industries. The linear systems of equation