Theorem proving using equational matings and rigid E -unification
Authors:
- Jean GallierJGJean Gallier
- Paliath NarendranPNPaliath Narendran
- Stan RaatzSRStan Raatz
- Wayne SnyderWSWayne Snyder
Open Access
- 1 April 1992
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 39 (2) , 377-430
Abstract
In this paper, it is shown that the method of matings due to Andrews and Bibel can be extended to (first-order) languages with equality. A decidable version of E -unification called rigid E-unification is introduced, and it is shown that the method of equational matings remains complete when used in conjunction with rigid E -unification. Checking that a family of mated sets is an equational mating is equivalent to the following restricted kind of E -unification. Problem Given E → ={E i | 1≤i≤n} a family of n finite sets of equations and S={〈u i ,v i 〉 |1≤i≤n} a set of n pairs of terms, is there a substitution θ such that, treating each set θ(E i ) as a set of ground equations (i.e., holding the variables in θ(E i ) “rigid”), θ(u i ), and θ(v i ) are provably equal from θ(E i ) for i=1,...,n? Equivalently, is there a substitution θ such that θ(u i ) and θ(v i ) can be shown congruent from θ(E i ) by the congruence closure method for i=1,...,n? A substitution θ solving the above problem is called a rigid E → -unifier of S , and a pair 〈E → ,S〉 such that S has some rigid E → -unifier is called an equational premating. It is shown that deciding whether a pair 〈 E → ,S〉is an equational premating is an NP-complete problem.Keywords
This publication has 16 references indexed in Scilit:
- Rigid E-unification: NP-completeness and applications to equational matingsInformation and Computation, 1990
- Complete sets of transformations for general E-unificationTheoretical Computer Science, 1989
- Existence, Uniqueness, and Construction of Rewrite SystemsSIAM Journal on Computing, 1988
- Termination of rewritingJournal of Symbolic Computation, 1987
- Linear logicTheoretical Computer Science, 1987
- Automating Higher-Order Logic1984
- On Matrices with ConnectionsJournal of the ACM, 1981
- Theorem Proving via General MatingsJournal of the ACM, 1981
- Variations on the Common Subexpression ProblemJournal of the ACM, 1980
- Tautology testing with a generalized matrix reduction methodTheoretical Computer Science, 1979