A Variant of the Superposition Calculus


Title: A Variant of the Superposition Calculus
Author: Nicolas Peltier
Submission date: 2016-09-06
Abstract: We provide a formalization of a variant of the superposition calculus, together with formal proofs of soundness and refutational completeness (w.r.t. the usual redundancy criteria based on clause ordering). This version of the calculus uses all the standard restrictions of the superposition rules, together with the following refinement, inspired by the basic superposition calculus: each clause is associated with a set of terms which are assumed to be in normal form -- thus any application of the replacement rule on these terms is blocked. The set is initially empty and terms may be added or removed at each inference step. The set of terms that are assumed to be in normal form includes any term introduced by previous unifiers as well as any term occurring in the parent clauses at a position that is smaller (according to some given ordering on positions) than a previously replaced term. The standard superposition calculus corresponds to the case where the set of irreducible terms is always empty.
  author  = {Nicolas Peltier},
  title   = {A Variant of the Superposition Calculus},
  journal = {Archive of Formal Proofs},
  month   = sep,
  year    = 2016,
  note    = {\url{http://isa-afp.org/entries/SuperCalc.shtml},
            Formal proof development},
  ISSN    = {2150-914x},
License: BSD License
Status: [ok] This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.