Computer Science – Artificial Intelligence
Scientific paper
2010-06-30
Computer Science
Artificial Intelligence
Scientific paper
Circumscription is a representative example of a nonmonotonic reasoning inference technique. Circumscription has often been studied for first order theories, but its propositional version has also been the subject of extensive research, having been shown equivalent to extended closed world assumption (ECWA). Moreover, entailment in propositional circumscription is a well-known example of a decision problem in the second level of the polynomial hierarchy. This paper proposes a new Boolean Satisfiability (SAT)-based algorithm for entailment in propositional circumscription that explores the relationship of propositional circumscription to minimal models. The new algorithm is inspired by ideas commonly used in SAT-based model checking, namely counterexample guided abstraction refinement. In addition, the new algorithm is refined to compute the theory closure for generalized close world assumption (GCWA). Experimental results show that the new algorithm can solve problem instances that other solutions are unable to solve.
Grigore Radu
Janota Mikolas
Marques-Silva Joao
No associations
LandOfFree
Counterexample Guided Abstraction Refinement Algorithm for Propositional Circumscription does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Counterexample Guided Abstraction Refinement Algorithm for Propositional Circumscription, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counterexample Guided Abstraction Refinement Algorithm for Propositional Circumscription will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-154299