Description Logics That Count, and What They Can and Cannot Count

From International Center for Computational Logic

Toggle side column

Description Logics That Count, and What They Can and Cannot Count

Filippo De BortoliFilippo De Bortoli,  Franz BaaderFranz Baader
Filippo De Bortoli, Franz Baader
Description Logics That Count, and What They Can and Cannot Count
In Laura Kovacs, Konstantin Korovin, Giles Reger, eds., ANDREI-60. Automated New-era Deductive Reasoning Event in Iberia, volume 68 of EPiC Series in Computing, 1-25, 2020. EasyChair
  • KurzfassungAbstract
    Simple counting quantifiers that can be used to compare the number of role successors of an individual or the cardinality of a concept with a fixed natural number have been employed in Description Logics (DLs) for more than two decades under the respective names of number restrictions and cardinality restriction on concepts. Recently, we have considerably extended the expressivity of such quantifiers by allowing to impose set and cardinality constraints formulated in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA) on sets of role successors and concepts, respectively. We were able to prove that this extension does not increase the complexity of reasoning. In the present paper, we investigate the expressive power of the DLs obtained this way, using appropriate bisimulation characterizations and 0-1 laws as tools for distinguishing the expressiveness of different logics. In particular, we show that, in contrast to most classical DLs, these logics are no longer expressible in first-order predicate logic (FOL), and we characterize their first-order fragments. In most of our previous work on DLs with QFBAPA-based set and cardinality constraints we have employed finiteness restrictions on interpretations to ensure that the obtained sets are finite. Here we dispense with these restrictions to make the comparison with classical DLs, where one usually considers arbitrary models rather than finite ones, easier. It turns out that doing so does not change the complexity of reasoning.
  • Projekt:Project: QuantLA
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ BaBo-ANDREI60-20,
      author = {Franz {Baader} and Filippo {De Bortoli}},
      booktitle = {ANDREI-60. Automated New-era Deductive Reasoning Event in Iberia},
      doi = {https://doi.org/10.29007/ltzn},
      editor = {Laura {Kovacs} and Konstantin {Korovin} and Giles {Reger}},
      pages = {1--25},
      publisher = {EasyChair},
      series = {EPiC Series in Computing},
      title = {Description Logics That Count, and What They Can and Cannot Count},
      volume = {68},
      year = {2020},
    }