In the context of ontology-mediated querying with description logics (DLs), we study the data complexity of queries in which selected predicates can be closed (OMQCs). We provide a non-uniform analysis, aiming at a classification of the complexity into tractable and non-tractable for ontologies in the lightweight DLs DL-Lite and EL, and the expressive DL ALCHI. At the level of ontologies, we prove a dichotomy between FO-rewritable and coNP-complete for DL-Lite and between PTime and coNP-complete for EL. The meta problem of deciding tractability is proved to be in PTime. At the level of OMQCs, we show that there is no dichotomy (unless NP equals PTime) if both concept and role names can be closed. If only concept names can be closed, we tightly link the complexity of query evaluation to the complexity of surjective CSPs. We also identify a class of OMQCs based on ontologies formulated in DL-Lite that are guaranteed to be tractable and even FO-rewritable.

The Beth definability property, a well-known property from classical logic, is investigated in the context of description logics: if a general L-TBox implicitly defines an L-concept in terms of a given signature, where L is a description logic, then does there always exist over this signature an explicit definition in L for the concept? This property has been studied before and used to optimize reasoning in description logics. In this paper a complete classification of Beth definability is provided for extensions of the basic description logic ALC with transitive roles, inverse roles, role hierarchies, and/or functionality restrictions, both on arbitrary and on finite structures. Moreover, we present a tableau-based algorithm which computes explicit definitions of at most double exponential size. This algorithm is optimal because it is also shown that the smallest explicit definition of an implicitly defined concept may be double exponentially long in the size of the input TBox. Finally, if explicit definitions are allowed to be expressed in first-order logic, then we show how to compute them in single exponential time.

Editors/Supervisors: Walsh T

Abstract: Current standards on agent communication languages explain communication by changes in the mental states of agents. It is rather a striking issue that none of the popular agent middleware adheres to this semantics in a formal way. Therefore, this paper tries to close the gap between agent communication theory and practice by implementing a logic that is capable of representing agents' beliefs and intentions. An interesting property of this language, named , is that it is a hybrid of modal and description logics. Due to its description logic foundation, it can also be used as an ontology definition language. Thus, it is well suited for agents working on the semantic web. In this paper, a sound and complete decision algorithm as well as other reasoning services for the logic are presented. Finally, the application of the language in a multi‐agent development framework is discussed.