Rigid E-unification: NP-completeness and applications to equational matings

DOI10.1016/0890-5401(90)90061-LzbMath0709.68080WikidataQ29392267 ScholiaQ29392267MaRDI QIDQ921913

Paliath Narendran, Wayne Snyder, Jean H. Gallier, David Alan Plaisted

Publication date: 1990

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

zbMATH Keywords

unificationNP-completeequational matings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35)

Related Items (7)

Efficient ground completion ⋮ Linear and unit-resulting refutations for Horn theories ⋮ The undecidability of simultaneous rigid E-unification ⋮ A completion-based method for mixed universal and rigid E-unification ⋮ What you always wanted to know about rigid E-unification ⋮ Decidability and complexity of simultaneous rigid E-unification with one variable and related results ⋮ Logic with equality: Partisan corroboration and shifted pairing

Uses Software

• ETPS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear logic
• Termination of rewriting
• Linear unification
• About the rewriting systems produced by the Knuth-Bendix completion algorithm
• Principles of combinatorics
• Fast Decision Procedures Based on Congruence Closure
• Theorem Proving via General Matings
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Variations on the Common Subexpression Problem
• An Efficient Unification Algorithm
• Positive First-Order Logic Is NP-Complete

This page was built for publication: Rigid E-unification: NP-completeness and applications to equational matings