On the Expressive Power of Description Logics with Cardinality Constraints on Finite and Infinite Sets

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Abstract

In recent work we have extended the description logic (DL) ALCQ by means of more expressive number restrictions using numerical and set constraints stated in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA). It has been shown that reasoning in the resulting DL, called ALCSCC, is PSpace-complete without a TBox and ExpTime-complete w.r.t. a general TBox. The semantics of ALCSCC is defined in terms of finitely branching interpretations, that is, interpretations where every element has only finitely many role successors. This condition was needed since QFBAPA considers only finite sets. In this paper, we first introduce a variant of ALCSCC, called ALCSCC, in which we lift this requirement (inexpressible in first-order logic) and show that the complexity results for ALCSCC mentioned above are preserved. Nevertheless, like ALCSCC, ALCSCC is not a fragment of first-order logic. The main contribution of this paper is to give a characterization of the first-order fragment of ALCSCC. The most important tool used in the proof of this result is a notion of bisimulation that characterizes this fragment.

Details

OriginalspracheEnglisch
TitelFrontiers of Combining Systems - 12th International Symposium, FroCoS 2019, Proceedings
Redakteure/-innenAndreas Herzig, Andrei Popescu
Herausgeber (Verlag)Springer, Berlin [u. a.]
Seiten203-219
Seitenumfang17
ISBN (Print)9783030290061
PublikationsstatusVeröffentlicht - 2019
Peer-Review-StatusJa

Publikationsreihe

ReiheLecture Notes in Computer Science, Volume 11715
ISSN0302-9743

Konferenz

Titel12th International Symposium on Frontiers of Combining Systems, FroCoS 2019
Dauer4 - 6 September 2019
StadtLondon
LandGroßbritannien/Vereinigtes Königreich

Externe IDs

Scopus 85071934839
ORCID /0000-0002-4049-221X/work/142247949
ORCID /0000-0002-8623-6465/work/142251902

Schlagworte

DFG-Fachsystematik nach Fachkollegium

Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis

Bibliotheksschlagworte