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

Sebastian RudolphSebastian Rudolph, Lukas SchweizerLukas Schweizer

ISBN: 978-3-319-65340-2

Sebastian Rudolph, Lukas Schweizer
Not too Big, Not too Small…Complexities of Fixed-Domain Reasoning in First-Order and Description Logics
In Oliveira Eugénio, Gama João, Vale Zita, Lopes Cardoso Henrique, eds., Progress in Artificial Intelligence: Proceedings of the 18th EPIA Conference on Artificial Intelligence, EPIA 2017, Porto, Portugal,, volume 10423 of Lecture Notes in Computer Science, 695-708, September 2017. 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 re- mains NEXPTIME even for first-order logic, which is undecidable under the un- constrained 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.
Bemerkung: Note: Winner of the EPIA 2017 Best Paper Award.
Weitere Informationen unter:Further Information: Link
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{\ldots}Complexities} of Fixed-Domain
               Reasoning in First-Order and Description Logics},
  editor    = {Oliveira Eug{\'{e}}nio and Gama Jo{\~{a}}o and Vale Zita and
               Lopes Cardoso Henrique},
  booktitle = {Progress in Artificial Intelligence: Proceedings of the 18th
               {EPIA} Conference on Artificial Intelligence, {EPIA} 2017, Porto,
               Portugal,},
  series    = {Lecture Notes in Computer Science},
  volume    = {10423},
  publisher = {Springer},
  year      = {2017},
  month     = {September},
  pages     = {695-708}
}