Computing stable models for nonmonotonic existential rules
Despoina Magka, Markus Krötzsch, Ian Horrocks · 2013
In this work, we consider function-free existential rules extended with nonmonotonic negation under a stable model semantics. We present new acyclic-ity and stratification conditions that identify a large class of rule sets having finite, unique stable mod-els, and we show how the addition of constraints on the input facts can further extend this class. Check-ing these conditions is computationally feasible, and we provide tight complexity bounds. Finally, we demonstrate how these new methods allowed us to solve relevant reasoning problems over a real-world knowledge base from biochemistry using an off-the-shelf answer set programming engine. 1