License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.17
URN: urn:nbn:de:0030-drops-109612
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10961/
Go to the corresponding LIPIcs Volume Portal

Danielski, Daniel ; Kieronski, Emanuel

Finite Satisfiability of Unary Negation Fragment with Transitivity

pdf-format:
LIPIcs-MFCS-2019-17.pdf (0.5 MB)

Abstract

We show that the finite satisfiability problem for the unary negation fragment with an arbitrary number of transitive relations is decidable and 2-ExpTime-complete. Our result actually holds for a more general setting in which one can require that some binary symbols are interpreted as arbitrary transitive relations, some as partial orders and some as equivalences. We also consider finite satisfiability of various extensions of our primary logic, in particular capturing the concepts of nominals and role hierarchies known from description logic. As the unary negation fragment can express unions of conjunctive queries, our results have interesting implications for the problem of finite query answering, both in the classical scenario and in the description logics setting.

BibTeX - Entry

@InProceedings{danielski_et_al:LIPIcs:2019:10961,
  author =	{Daniel Danielski and Emanuel Kieronski},
  title =	{{Finite Satisfiability of Unary Negation Fragment with Transitivity}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10961},
  URN =		{urn:nbn:de:0030-drops-109612},
  doi =		{10.4230/LIPIcs.MFCS.2019.17},
  annote =	{Keywords: unary negation fragment, transitivity, finite satisfiability, finite open-world query answering, description logics}
}

Keywords: unary negation fragment, transitivity, finite satisfiability, finite open-world query answering, description logics
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI