7th International Conference on Automated Deduction Proceedings

The Seventh International Conference on Automated Deduction was held May 14-16, 19S4, in Napa, California. The conference is the primary forum for reporting research in all aspects of automated deduction, including the design, implementation, and applications of theorem-proving systems, knowledge representation and retrieval, program verification, logic programming, formal specification, program synthesis, and related areas. The presented papers include 27 selected by the program committee, an invited keynote address by Jorg Siekmann, and an invited banquet address by Patrick Suppes. Contributions were presented by authors from Canada, France, Spain, the United Kingdom , the United States, and West Germany. The first conference in this series was held a decade earlier in Argonne, Illinois. Following the Argonne conference were meetings in Oberwolfach, West Germany (1976), Cambridge, Massachusetts (1977), Austin, Texas (1979), Les Arcs, France (19S0), and New York, New York (19S2). Program Committee P. Andrews (CMU) W.W. Bledsoe (U. Texas) past chairman L. Henschen (Northwestern) G. Huet (INRIA) D. Loveland (Duke) past chairman R. Milner (Edinburgh) R. Overbeek (Argonne) T. Pietrzykowski (Acadia) D. Plaisted (U. Illinois) V. Pratt (Stanford) R. Shostak (SRI) chairman J. Siekmann (U. Kaiserslautern) R. Waldinger (SRI) Local Arrangements R. Schwartz (SRI) iv CONTENTS Monday Morning Universal Unification (Keynote Address) Jorg H. Siekmann (FRG) .

Universal Unification.- A Portable Environment for Research in Automated Reasoning.- A Natural Proof System Based on Rewriting Techniques.- EKL—A Mathematically Oriented Proof Checker.- A Linear Characterization of NP-Complete Problems.- A Satisfiability Tester for Non-Clausal Propositional Calculus.- A Decision Method for Linear Temporal Logic.- A Progress Report on New Decision Algorithms for Finitely Presented Abelian Groups.- Canonical Forms in Finitely Presented Algebras.- Term Rewriting Systems and Algebra.- Termination of a Set of Rules Modulo a Set of Equations.- Associative-Commutative Unification.- A Linear Time Algorithm for a Subcase of Second Order Instantiation.- A New Equational Unification Method: A Generalisation of Martelli-Montanari’s Algorithm.- A Case Study of Theorem Proving by the Knuth-Bendix Method: Discovering that x 3 = x Implies Ring Commutativity.- A Narrowing Procedure for Theories with Constructors.- A General Inductive Completion Algorithm and Application to Abstract Data Types.- The Next Generation of Interactive Theorem Provers.- The Linked Inference Principle, II: The User’s Viewpoint.- A New Interpretation of the Resolution Principle.- Using Examples, Case Analysis, and Dependency Graphs in Theorem Proving.- Expansion Tree Proofs and Their Conversion to Natural Deduction Proofs.- Analytic and Non-analytic Proofs.- Applications of Protected Circumscription.- Implementation Strategies for Plan-Based Deduction.- A Programming Notation for Tactical Reasoning.- The Mechanization of Existence Proofs of Recursive Predicates.- Solving Word Problems in Free Algebras Using Complexity Functions.- Solving a Problem in Relevance Logic with an Automated Theorem Prover.