Combining Description Logics, Description Graphs, and Rules

Recent practical experience with description logics (DLs) has revealed that their expressivity is often insufficient to accurately describe structured objects-objects whose parts are interconnected in arbitrary, rather than tree-like ways. To address this problem, we propose an extension of DL languages with description graphs-a modeling construct that call accurately describe objects whose parts are connected in arbitrary ways. Furthermore, to enable modeling the conditional aspects of structured objects, we also incorporate rules into our formalism. We present all in-depth study of the computational properties of such a formalism. In particular, we first identify the sources of undecidability of the general, unrestricted formalism, and then present a restriction that makes reasoning decidable. Finally, we present tight complexity bounds.