Lecture Notes in Computer Science, 2000, Volume 1861/2000, 583-597, DOI: 10.1007/3-540-44957-4_39

An Application of Model Building in a Resolution Decision Procedure for Guarded Formulas

Michael Dierkes

View Related Documents

Abstract

Semantic resolution refinements are a very efficient way to restrict the resolution rule. Their principle is to avoid resolution between clauses that are true in a certain interpretation. In this way, the number of deduced clauses can be decreased drastically, and deduction can be restricted to clauses that are interesting from a semantic point of view. In this article, we present a semantic refinement of a resolution decision procedure for formulas of the guarded fragment (without equality). This fragment of first-order logic was introduced in [1] in order to explain the nice properties (in particular decidability) of propositional modal logics. In fact, many modal logics can be translated into the guarded fragment. Guarded clauses, defined in [8], are a generalization of guarded formulas in clausal form and decidable by resolution. The method presented in this article uses a model building procedure for guarded clauses which contain a positive maximal literal. A set of such clauses can be derived from the guarded clause set under consideration.

Fulltext Preview

Image of the first page of the fulltext document