Affordable Access

Publisher Website

On strongest necessary and weakest sufficient conditions☆☆ An earlier version of this paper was the co-winner of the Best Paper Award at KR2000.

Authors
Journal
Artificial Intelligence
0004-3702
Publisher
Elsevier
Publication Date
Volume
128
Identifiers
DOI: 10.1016/s0004-3702(01)00070-4
Keywords
  • Automated Reasoning
  • Definability
  • Abduction
Disciplines
  • Computer Science
  • Logic

Abstract

Abstract Given a propositional theory T and a proposition q, a sufficient condition of q is one that will make q true under T, and a necessary condition of q is one that has to be true for q to be true under T. In this paper, we propose a notion of strongest necessary and weakest sufficient conditions. Intuitively, the strongest necessary condition of a proposition is the most general consequence that we can deduce from the proposition under the given theory, and the weakest sufficient condition is the most general abduction that we can make from the proposition under the given theory. We show that these two conditions are dual ones, and can be naturally extended to arbitrary formulas. We investigate some computational properties of these two conditions and discuss some of their potential applications.

There are no comments yet on this publication. Be the first to share your thoughts.