1 Search Results for "Danielski, Daniel"

Document
DOI: 10.4230/LIPIcs.MFCS.2019.17
Finite Satisfiability of Unary Negation Fragment with Transitivity

Authors: Daniel Danielski and Emanuel Kieroński

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

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.
Cite as

Daniel Danielski and Emanuel Kieroński. Finite Satisfiability of Unary Negation Fragment with Transitivity. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{danielski_et_al:LIPIcs.MFCS.2019.17,
  author =	{Danielski, Daniel and Kiero\'{n}ski, Emanuel},
  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 =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.17},
  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}
}
  • Refine by Author
  • 1 Danielski, Daniel
  • 1 Kieroński, Emanuel

  • Refine by Classification
  • 1 Theory of computation → Logic

  • Refine by Keyword
  • 1 description logics
  • 1 finite open-world query answering
  • 1 finite satisfiability
  • 1 transitivity
  • 1 unary negation fragment

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact