Bridging the Gap Between Classical Logic Based Formalisms and Logic Programs

Different logic-based knowledge representation formalisms have different limitations either with respect to expressivity or with respect to computational efficiency. First-order logic, which is the basis of Description Logics (DLs), is not suitable for defeasible reasoning due to its monotonic nature. The nonmonotonic formalisms that extend first-order logic, such as circumscription and default logic, are expressive but lack efficient implementations. The nonmonotonic formalisms that are based on the declarative logic programming approach, such as Answer Set Programming (ASP), have efficient implementations but are not expressive enough for representing and reasoning with open domains.

We use the first-order stable model semantics, which extends both first-order logic and ASP, to relate circumscription to ASP, and to integrate DLs and ASP, thereby partially overcoming the limitations of the formalisms. By exploiting the relationship between circumscription and ASP, we show how well-known action formalisms, such as the situation calculus, the event calculus, and Temporal Action Logics, can be reformulated in ASP. We show that these reformulations have certain advantages with respect to the generality of the reasoning tasks that can be handled and with respect to the computational efficiency. Our integration of DLs and ASP enables us to perform nonmonotonic reasoning with DL knowledge bases and provides a framework for integrating rules and ontologies for the semantic web. Observing the need to integrate action theories and ontologies, we use the above results to reformulate the problem of integrating action theories and ontologies as a problem of integrating rules and ontologies, thus enabling us to use the computational tools developed in the context of the latter for the former.