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

From International Center for Computational Logic

Toggle side column

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

Filippo De BortoliFilippo De Bortoli,  Franz BaaderFranz Baader
On the Expressive Power of Description Logics with Cardinality Constraints on Finite and Infinite Sets


Filippo De Bortoli, Franz Baader
On the Expressive Power of Description Logics with Cardinality Constraints on Finite and Infinite Sets
In Andreas Herzig, Andrei Popescu, eds., Proc. of the 12th International Symposium on Frontiers of Combining Systems (FroCoS 2019), volume 11715 of Lecture Notes in Computer Science, 203-219, 2019. Springer
  • KurzfassungAbstract
    In recent work we have extended the description logic (DL) 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.
  • Projekt:Project: QuantLA
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
The final publication is available at Springer.
@inproceedings{ BaDeBo-FroCoS19,
      author = {Franz {Baader} and Filippo {De Bortoli}},
      booktitle = {Proc. of the 12th International Symposium on Frontiers of Combining Systems ({FroCoS} 2019)},
      doi = {https://doi.org/10.1007/978-3-030-29007-8_12},
      editor = {Andreas {Herzig} and Andrei {Popescu}},
      pages = {203--219},
      publisher = {Springer},
      series = {Lecture Notes in Computer Science},
      title = {On the Expressive Power of Description Logics with Cardinality Constraints on Finite and Infinite Sets},
      volume = {11715},
      year = {2019},
    }