The Curse of Finiteness: Undecidability of Database-Inspired Reasoning Problems in Very Expressive Description Logics

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

The Curse of Finiteness: Undecidability of Database-Inspired Reasoning Problems in Very Expressive Description Logics

Sebastian RudolphSebastian Rudolph
Sebastian Rudolph
The Curse of Finiteness: Undecidability of Database-Inspired Reasoning Problems in Very Expressive Description Logics
In Maurizio Lenzerini, Rafael Peñaloza, eds., Proceedings of the 29th International Workshop on Description Logics (DL'16), volume 1577, 2016. CEUR Workshop Proceedings
  • KurzfassungAbstract
    Recently, the field of knowledge representation is drawing a lot of inspiration from database theory. In particular, in the area of description logics and ontology languages, interest has shifted from satisfiability checking to query answering, with various query notions adopted from databases, like (unions of) conjunctive queries or different kinds of path queries. Likewise, the finite model semantics is being established as a viable and interesting alternative to the tradi- tional semantics based on unrestricted models.

    In this paper, we investigate diverse database-inspired reasoning problems for very expressive description logics (all featuring the worrisome triad of inverses, counting, and nominals) which have in common that role paths of unbounded length can be described (in the knowledge base or of the query), leading to a certain non-locality of the reasoning problem. We show that for all the cases considered, undecidability can be established by very similar means.

    Most notably, we show undecidability of finite entailment of unions of conjunc- tive queries for a fragment of SHOIQ (the logic underlying the OWL DL ontology language), and undecidability of finite entailment of conjunctive queries for a fragment of SROIQ (the logical basis of the more recent and popular OWL 2 DL standard).
  • Weitere Informationen unter:Other info: Link
  • Forschungsgruppe:Research Group: Computational Logic
@inproceedings{R2016,
  author    = {Sebastian Rudolph},
  title     = {The Curse of Finiteness: Undecidability of Database-Inspired
               Reasoning Problems in Very Expressive Description Logics},
  editor    = {Maurizio Lenzerini and Rafael Pe{\~{n}}aloza},
  booktitle = {Proceedings of the 29th International Workshop on Description
               Logics (DL'16)},
  volume    = {1577},
  publisher = {CEUR Workshop Proceedings},
  year      = {2016}
}