Inproceedings3151

PublikationenPublications

• Nach AutorBy Author
  • Sebastian RudolphSebastian Rudolph
  • Lukas SchweizerLukas Schweizer
• Nach ForschungsgruppeBy Research Group
  • Computational LogicComputational Logic

Toggle side column

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
Proceedings of the 18th EPIA Conference on Artificial Intelligence (EPIA 2017), 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 = {Proceedings of the 18th {EPIA} Conference on Artificial
               Intelligence (EPIA 2017)},
  publisher = {Springer},
  year      = {2017},
  month     = {September}
}