Production systems with negation as failure
Phan Minh Dũng, Paolo Mancarella · IEEE Transactions on Knowledge and Data Engineering · 2002
We study action rule-based systems with two forms of negation, namely classical negation and "negation as failure to find a course of action". We show, by means of several examples, that adding negation as failure to such systems increases their expressiveness in the sense that real-life problems can be represented in a natural and simple way. Then we address the problem of providing a formal declarative semantics to these extended systems by adopting an argumentation-based approach which has been shown to be a simple unifying framework for understanding the declarative semantics of various nonmonotonic formalisms. In this way, we naturally define the grounded (well-founded), stable and preferred semantics for production systems with negation as failure. Next, we characterize the class of stratified production systems, which enjoy the properties that the above-mentioned semantics coincide and that negation as failure to find a course of action can be computed by a simple bottom-up operator. Stratified production systems can be implemented on top of conventional production systems in two ways. The first way corresponds to the understanding of stratification as a form of priority assignment between rules. We show that this implementation, though sound, is not complete in the general case. Hence, we propose a second implementation by means of an algorithm which transforms a finite stratified production system into a classical one. This is a sound and complete implementation, though it is computationally hard.