Not too Big, Not too Small ... Complexities of Fixed-Domain Reasoning in First-Order and Description Logics

Sebastian RudolphSebastian Rudolph, Lukas SchweizerLukas Schweizer

Download

Sebastian Rudolph, Lukas Schweizer
Not too Big, Not too Small ... Complexities of Fixed-Domain Reasoning in First-Order and Description Logics
Lecture Notes in Artificial Intelligence, volume 10423, to appear. Springer

Details
Bibtex

KurzfassungAbstract
We consider reasoning problems in description logics and variants of first-order logic under the fixed-domain semantics, where the model size is finite and explicitly given. It follows from previous results that standard reasoning is NP-complete for a very wide range of logics, if the domain size is given in unary encoding. In this paper, we complete the complexity overview for unary encoding and investigate the effects of binary encoding with partially surprising results. Most notably, fixed-domain standard reasoning becomes NExpTime for the rather low-level description logics ELI and ELF (as opposed to ExpTime when no domain size is given). On the other hand, fixed-domain reasoning remains NExpTime even for first-order logic, which is undecidable under the unconstrained semantics. For less expressive logics, we establish a generic criterion ensuring NP-completeness of fixed-domain reasoning. Amongst other logics, this criterion captures all the tractable profiles of OWL 2.
Projekt:Project: QuantLA
Forschungsgruppe:Research Group: Computational LogicComputational Logic

The final publication is available at Springer.

@inproceedings{RS2017,
  author    = {Sebastian Rudolph and Lukas Schweizer},
  title     = {Not too Big, Not too Small ... Complexities of Fixed-Domain
               Reasoning in First-Order and Description Logics},
  booktitle = {Lecture Notes in Artificial Intelligence},
  volume    = {10423},
  publisher = {Springer},
  year      = {2017},
  month     = {September}
}