liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Computing circumscription revisited : A reduction algorithm
1997 (English)In: Journal of automated reasoning, ISSN 0168-7433, E-ISSN 1573-0670, Vol. 18, no 3, 297-336Article in journal (Refereed) Published
Abstract [en]

In recent years, a great deal of attention has been devoted to logics of common-sense reasoning. Among the candidates proposed, circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic reasoning, but difficult to apply in practice. The major reason for this is the second-order nature of circumscription axioms and the difficulty in finding proper substitutions of predicate expressions for predicate variables. One solution to this problem is to compile, where possible, second-order formulas into equivalent first-order formulas. Although some progress has been made using this approach, the results are not as strong as one might desire and they are isolated in nature. In this article, we provide a general method that can be used in an algorithmic manner to reduce certain circumscription axioms to first-order formulas. The algorithm takes as input an arbitrary second-order formula and either returns as output an equivalent first-order formula, or terminates with failure. The class of second-order formulas, and analogously the class of circumscriptive theories that can be reduced, provably subsumes those covered by existing results. We demonstrate the generality of the algorithm using circumscriptive theories with mixed quantifiers (some involving Skolemization), variable constants, nonseparated formulas, and formulas with n-ary predicate variables. In addition, we analyze the strength of the algorithm, compare it with existing approaches, and provide formal subsumption results.

National Category
Computer Science
URN: urn:nbn:se:liu:diva-41623DOI: 10.1023/A:1005722130532Local ID: 58416OAI: diva2:262477
Available from2009-10-10 Created:2009-10-10 Last updated:2012-02-13

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Doherty, PatrickLukaszewicz, WitoldSzalas, Andrzej
By organisation
The Institute of TechnologyKPLAB - Knowledge Processing Lab
In the same journal
Journal of automated reasoning
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link