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

Sebastian RudolphSebastian Rudolph

Download

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

Details
Bibtex

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:Further Information: Link
Forschungsgruppe:Research Group: Computational LogicComputational 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}
}