文章基本信息

标题：Finite Satisfiability of Unary Negation Fragment with Transitivity
本地全文：下载
作者：Daniel Danielski ; Emanuel Kieronski
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-15
DOI：10.4230/LIPIcs.MFCS.2019.17
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：unary negation fragment; transitivity; finite satisfiability; finite open-world query answering; description logics