KR Conference 2012 Conference Paper
- Hanne Vlaeminck
- Joost Vennekens
- Maurice Bruynooghe
- Marc Denecker
these logics is a theory that refers to its own information content through a reflexive epistemic operator (see (Denecker, Marek, and Truszczynski 2011) for a recent account). This is a source of complexity that complicates both their semantics and their reasoning procedures. By contrast, OEL maintains a stratified representation where each level extends the knowledge of the lower levels. This simplifies the logic considerably, while still being able to handle a lot of useful applications from AEL or DL, as we will show here. Contrary to AEL, DL or ASP, an OEL theory always defines a unique belief set, represented as a set of possible worlds. We will show that OEL solves some well-known problems of ASP in the context of epistemic applications. Syntactically, OEL extends FO; the only difference with FO is that OEL is a closed domain version of FO: all possible worlds share the same domain and interpretation of terms, like many first order modal logics. With exception of this feature, OEL is a conservative extension of FO; its epistemic operator stands orthogonal to many other extensions of FO (e. g., types, inductive definitions, aggregates,...), and hence seamlessly integrates with them. Our examples here will include such extensions. By combining them, a very rich KR language is obtained in which many of the motivating examples in DL, AEL and ASP, as well as other extensions of FO such as FO(ID) (Denecker and Ternovska 2008), have a natural expression. We here extend the initial work in (Konolige 1988a; Denecker et al. 2010), in several ways. First, we prove that, in a given finite domain, the data complexity of model checking, satisfiability checking and query answering for OEL theories is in ∆P 2, which is indeed lower then for AEL and DL, where some instances of satisfiability checking problems can be proven to be ΣP 2 -complete. We also show how a model generator for OEL can be implemented. Second, we illustrate the use of OEL and of model generation in the context of a scheduling problem with an epistemic component. Third, we extend OEL to a logic for distributed epistemic agents, which we call distributed ordered epistemic logic (d-OEL). Knowledge bases are still hierarchically ordered, but now theories at one level no longer automatically possess all the knowledge of lower levels. Distributed ordered epistemic logic can cope with distributed knowledge, which makes it relevant for a number of new application areas. One example is the specification Many examples of epistemic reasoning in the literature exhibit a stratified structure: defaults are formulated on top of an incomplete knowledge base. These defaults derive extra information in case information is missing in the knowledge base. In autoepistemic logic, default logic and ASP this inherent stratification is not preserved as they may refer to their own knowledge or logical consequences. Defining the semantics of such logics requires a complex mathematical construction. As an alternative, this paper further develops ordered epistemic logic. This logic extends first order logic with a modal operator and stratification is maintained. This allows us to define an easy to understand semantics. Moreover, inference tasks have a lower complexity than in autoepistemic logic and the logic integrates seamlessly into classical logic and its extensions. In this paper we also propose a generalization of ordered epistemic logic, which we call distributed ordered epistemic logic. We argue that it can provide a semantic foundation for a number of distributed knowledge representation formalisms found in the literature.