Computing circumscription revisited: preliminary report
Patrick Doherty, Witold Łukaszewicz, Andrzej Szałas · 1995
We provide a general method which can be used in an algorithmic manner to reduce certain classes of 2nd-order circumscription axioms to logically equivalent 1st-order formulas. The algorithm takes as input an arbitrary 2nd-order formula and either returns as output an equivalent 1st-order formula, or terminates with failure. In addition to demonstrating the algorithm by applying it to various circumscriptive theories, we analyze its strength and provide formal subsumption results based on comparison with existing approaches. 1 Introduction and Preliminaries In recent years, a great deal of attention has been devoted to logics of "commonsense" reasoning. Among the candidates proposed, circumscription [ Lifschitz, 1994 ] , has been perceived as an elegant mathematical technique for modeling nonmonotonic reasoning, but difficult to apply in practice. Practical application of circumscription is made difficult due to two problems. The first concerns the difficulty in finding the proper cir...