Author name cluster

Mantas Šimkus

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

17 papers

1 author row

AIJ Journal 2026 Journal Article

SHACL validation in the presence of ontologies: Semantics and rewriting techniques

Anouk Oudshoorn
Magdalena Ortiz
Mantas Šimkus

SHACL and OWL are two prominent W3C standards for managing RDF data. These languages share many features, but they have one fundamental difference: OWL, designed for inferring facts from incomplete data, makes the open-world assumption, whereas SHACL is a constraint language that treats the data as complete and must be validated under the closed-world assumption. The combination of both formalisms is very appealing and has been called for, but their semantic gap is a major challenge, semantically and computationally. In this paper, we advocate a semantics for SHACL validation in the presence of ontologies based on core universal models. We provide a technique for constructing these models for ontologies in the rich data-tractable description logic Horn-ALCHIQ. Furthermore, we use a finite representation of this model to develop a rewriting technique that reduces SHACL validation in the presence of ontologies to standard validation. Finally, we study the complexity of SHACL validation in the presence of ontologies, and show that even very simple ontologies make the problem EXPTIME-complete, and PTIME-complete in data complexity.

Details DOI

KR Conference 2025 Conference Paper

Expressive Description Logics with Rich Yet Affordable Numeric Constraints

Federica Di Stefano
Sanja Lukumbuzya
Magdalena Ortiz
Mantas Šimkus

Description Logics (DLs) excel at representing structured knowledge in several application domains, but fall very short when it comes to reasoning about their numeric aspects. We consider the expressive DL ALCHOIQ with closed predicates and extend it with features ranging over user-specified finite numeric intervals, feature assertions, and local additive constraints on feature values. We illustrate the power of this language for describing problems that involve ontological and numeric reasoning and study reasoning problems that go beyond satisfiability, such as finding models that minimize some costs. We show that these additional numeric modeling and reasoning capabilities can be accommodated by extending a standard reasoning technique for ALCHOIQ using linear inequalities, and the extension does not necessarily increase the worst-case computational cost.

PDF Details DOI

KR Conference 2025 Conference Paper

Minimal Model Reasoning in Description Logics: Don’t Try This at Home!

Federica Di Stefano
Quentin Manière
Magdalena Ortiz
Mantas Šimkus

Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates---letting the remaining predicates vary or be fixed, as proposed in circumscription---has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. We address this problem in popular DLs and obtain surprisingly negative results: concept satisfiability in minimal models is undecidable already for EL. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite_core, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite_horn.

PDF Details DOI

AIJ Journal 2024 Journal Article

Datalog rewritability and data complexity of ALCHOIQ with closed predicates

Sanja Lukumbuzya
Magdalena Ortiz
Mantas Šimkus

We study the relative expressiveness of ontology-mediated queries (OMQs) formulated in the expressive Description Logic ALCHOIQ extended with closed predicates. In particular, we present a polynomial time translation from OMQs into Datalog with negation under the stable model semantics, the formalism that underlies Answer Set Programming. This is a novel and non-trivial result: the considered OMQs are not only non-monotonic, but also feature a tricky combination of nominals, inverse roles, and counting. We start with atomic queries and then lift our approach to a large class of first-order queries where quantification is “guarded” by closed predicates. Our translation is based on a characterization of the query answering problem via integer programming, and a specially crafted program in Datalog with negation that finds solutions to dynamically generated systems of integer inequalities. As an important by-product of our translation we get that the query answering problem is co-NP-complete in data complexity for the considered class of OMQs. Thus, answering these OMQs in the presence of closed predicates is not harder than answering them in the standard setting. This is not obvious as closed predicates are known to increase data complexity for some existing ontology languages.

Details DOI

KR Conference 2024 Conference Paper

Equilibrium Description Logics: Results on Complexity and Relations to Circumscription

Federica Di Stefano
Mantas Šimkus

Recently, Equilibrium Description Logics (EDLs) have been suggested as a promising new approach to Description Logics (DLs) with non-monotonic default negation. However, a deeper understanding of EDLs in terms of computational complexity and relations to other formalisms is still missing. Motivated by this, in this paper we investigate the computational complexity of reasoning in EDLs both in the case of expressive DLs like ALCIO and lightweight DLs in the EL and DL-Lite families. We establish a translation on EDLs into DLs with circumscription, introducing an extension of circumscribed DLs where a further set of axioms is attached to circumscribed KBs to filter out unintended minimal models. Such translation not only applies in the case of classical circumscription but can be extended to the recently introduced pointwise circumscribed DLs. We introduce pointwise EDLs where the single global minimality check on models is replaced by local minimality checks at the single domain elements in the style of pointwise circumscription. We provide preliminary results on the computational complexity of reasoning in pointwise EDLs. In particular, via the translation into pointwise circumscription, we inherit the decidability results of pointwise circumscribed DLs. Furthermore, we show that for a large class of acyclic ontologies EDLs and pointwise EDLs accept the same set of stable models. To this aim, we identify a class of ontologies where circumscription and pointwise circumscription accept the same set of minimal models, providing new decidability results for circumscribed DLs even in the presence of minimized and fixed roles.

PDF Details DOI

KR Conference 2024 Conference Paper

SHACL Validation under the Well-founded Semantics

Cem Okulmus
Mantas Šimkus

W3C has recently introduced SHACL as a new standard for writing integrity constraints on graph-structured data (specifically, on RDF graphs). Unfortunately, the standard defines the semantics of non-recursive constraints only, leaving the case of recursive constraints open. This has spurred recent research efforts into finding a suitable, mathematically crisp semantics for constraints with cyclic dependencies. In this paper, we argue that recursive SHACL can be naturally equipped with a semantics inspired in the well-founded semantics for recursive logic programs with default negation. This semantics is not only intuitive, but it is also computationally tractable, unlike the previous proposals. The semantics is tolerant to constraint violations that are outside the realm of the so-called validation targets, which is a feature that is highly relevant in practice. In addition to defining the well-founded semantics using a notion of unfounded sets, we draw a connection to the classic definition of the well-founded semantics in logic programming: we provide a simple (yet inefficient) translation of recursive SHACL under the well-founded semantics into propositional logic programs under the well-founded semantics. This translation also provides a basis for a highly optimized SHACL validation engine, which we also present in this paper. Our system performs graph validation by producing a optimized logic program that can be evaluated using the DLV deductive database engine. The system has pay-as-you-go behavior: for validation with non-recursive constraints, the system avoids using a deductive database and instead only uses SPARQL queries over a RDF triplestore.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Stable Model Semantics for Description Logic Terminologies

Federica Di Stefano
Mantas Šimkus

This paper studies a stable model semantics for Description Logic (DL) knowledge bases (KBs) and for (possibly cyclic) terminologies, ultimately showing that terminologies under the proposed semantics can be equipped with effective reasoning algorithms. The semantics is derived using Quantified Equilibrium Logic, and---in contrast to the usual semantics of DLs based on classical logic---supports default negation and allows to combine the open-world and the closed-world assumptions in a natural way. Towards understanding the computational properties of this and related formalisms, we show a strong undecidability result that applies not only to KBs under the stable model semantics, but also to the more basic setting of minimal model reasoning. Specifically, we show that concept satisfiability in minimal models of an ALCIO KB is undecidable. We then turn our attention to (possibly cyclic) DL terminologies, where ontological axioms are limited to definitions of concept names in terms of complex concepts. This restriction still yields a very rich setting. We show that standard reasoning problems, like concept satisfiability and subsumption, are ExpTime-complete for terminologies expressed in ALCI under the stable model semantics.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Description Logics with Pointwise Circumscription

Federica Di Stefano
Magdalena Ortiz
Mantas Šimkus

Circumscription is one of the most powerful ways to extend Description Logics (DLs) with non-monotonic reasoning features, albeit with huge computational costs and undecidability in many cases. In this paper, we introduce pointwise circumscription for DLs, which is not only intuitive in terms of knowledge representation, but also provides a sound approximation of classic circumscription and has reduced computational complexity. Our main idea is to replace the second-order quantification step of classic circumscription with a series of (pointwise) local checks on all domain elements and their immediate neighbourhood. Our main positive results are for ontologies in DLs ALCIO and ALCI: we prove that for TBoxes of modal depth 1 (i. e. without nesting of existential or universal quantifiers) standard reasoning problems under pointwise circumscription are (co)NExpTime-complete and ExpTime-complete, respectively. The restriction of modal depth still yields a large class of ontologies useful in practice, and it is further justified by a strong undecidability result for pointwise circumscription with general TBoxes in ALCIO.

PDF Details DOI

KR Conference 2021 Conference Paper

Reasoning about Explanations for Non-validation in SHACL

Shqiponja Ahmetaj
Robert David
Magdalena Ortiz
Axel Polleres
Bojken Shehu
Mantas Šimkus

The Shapes Constraint Language (SHACL) is a recently standardized language for describing and validating constraints over RDF graphs. The SHACL specification describes the so-called validation reports, which are meant to explain to the users the outcome of validating an RDF graph against a collection of constraints. Specifically, explaining the reasons why the input graph does not satisfy the constraints is challenging. In fact, the current SHACL standard leaves it open on how such explanations can be provided to the users. In this paper, inspired by works on logic-based abduction and database repairs, we study the problem of explaining non-validation of SHACL constraints. In particular, in our framework non-validation is explained using the notion of a repair, i. e. , a collection of additions and deletions whose application on an input graph results in a repaired graph that does satisfy the given SHACL constraints. We define a collection of decision problems for reasoning about explanations, possibly restricting to explanations that are minimal with respect to cardinality or set inclusion. We provide a detailed characterization of the computational complexity of those reasoning tasks, including the combined and the data complexity.

PDF Details DOI

KR Conference 2020 Conference Paper

An ExpTime Upper Bound for ALC with Integers

Nadia Labai
Magdalena Ortiz
Mantas Šimkus

Concrete domains, especially those that allow to compare features with numeric values, have long been recognized as a very desirable extension of description logics (DLs), and significant efforts have been invested into adding them to usual DLs while keeping the complexity of reasoning in check. For expressive DLs and in the presence of general TBoxes, for standard reasoning tasks like consistency, the most general decidability results are for the so-called ω-admissible domains, which are required to be dense. Supporting non-dense domains for features that range over integers or natural numbers remained largely open, despite often being singled out as a highly desirable extension. The decidability of some extensions of ALC with non-dense domains has been shown, but existing results rely on powerful machinery that does not allow to infer any elementary bounds on the complexity of the problem. In this paper, we study an extension of ALC with a rich integer domain that allows for comparisons (between features, and between features and constants coded in unary), and prove that consistency can be solved using automata-theoretic techniques in single exponential time, and thus has no higher worst-case complexity than standard ALC. Our upper bounds apply to some extensions of DLs with concrete domains known from the literature, support general TBoxes, and allow for comparing values along paths of ordinary (not necessarily functional) roles.

PDF Details DOI

KR Conference 2020 Conference Paper

Datalog Rewritability and Data Complexity of ALCHOIF with Closed Predicates

Tomasz Gogacz
Sanja Lukumbuzya
Magdalena Ortiz
Mantas Šimkus

We study the relative expressiveness of ontology-mediated queries (OMQs) formulated in the expressive Description Logic ALCHOIF extended with closed predicates. In particular, we present a polynomial-time translation from OMQs into Datalog with negation under the stable model semantics, the formalism that underlies Answer Set Programming. This is a novel and non-trivial result: the considered OMQs are not only non-monotonic but also feature a tricky combination of nominals, inverse roles, and role functionality. We start with atomic queries and then lift our approach to a large class of first-order queries where quantification is “guarded” by closed predicates. Our translation is based on a characterization of the query answering problem via integer programming, and a specially crafted program in Datalog with negation that finds solutions to dynamically generated systems of integer inequalities. As an important by-product of our translation, we get that the query answering problem is co-NP-complete in data complexity for the considered class of OMQs. Thus, answering these OMQs in the presence of closed predicates is not harder than answering them in the standard setting. This is not obvious as closed predicates are known to increase data complexity for some existing ontology languages.

PDF Details DOI

AIJ Journal 2020 Journal Article

Polynomial rewritings from expressive Description Logics with closed predicates to variants of Datalog

Shqiponja Ahmetaj
Magdalena Ortiz
Mantas Šimkus

In many scenarios, complete and incomplete information coexist. For this reason, the knowledge representation and database communities have long shown interest in simultaneously supporting the closed- and the open-world views when reasoning about logic theories. Here we consider the setting of querying possibly incomplete data using logic theories, formalized as the evaluation of an ontology-mediated query (OMQ) that pairs a query with a theory, sometimes called an ontology, expressing background knowledge. This can be further enriched by specifying a set of closed predicates from the theory that are to be interpreted under the closed-world assumption, while the rest are interpreted with the open-world view. In this way we can retrieve more precise answers to queries by leveraging the partial completeness of the data. The central goal of this paper is to understand the relative expressiveness of ontology-mediated query languages in which the ontology part is written in the expressive Description Logic (DL) ALCHOI and includes a set of closed predicates. We consider a restricted class of conjunctive queries. Our main result is to show that every query in this non-monotonic query language can be translated in polynomial time into Datalog with negation as failure under the stable model semantics. To overcome the challenge that Datalog has no direct means to express the existential quantification present in ALCHOI, we define a two-player game that characterizes the satisfaction of the ontology, and design a Datalog query that can decide the existence of a winning strategy for the game. If there are no closed predicates—in the case of querying an ALCHOI knowledge base—our translation yields a positive disjunctive Datalog program of polynomial size. To the best of our knowledge, unlike previous translations for related fragments with expressive (non-Horn) DLs, these are the first polynomial time translations.

Details DOI

AAAI Conference 2020 Conference Paper

Resilient Logic Programs: Answer Set Programs Challenged by Ontologies

Sanja Lukumbuzya
Magdalena Ortiz
Mantas Šimkus

We introduce resilient logic programs (RLPs) that couple a non-monotonic logic program and a ﬁrst-order (FO) theory or description logic (DL) ontology. Unlike previous hybrid languages, where the interaction between the program and the theory is limited to consistency or query entailment tests, in RLPs answer sets must be ‘resilient’ to the models of the theory, allowing non-output predicates of the program to respond differently to different models. RLPs can elegantly express ∃∀∃-QBFs, disjunctive ASP, and conﬁguration problems under incompleteness of information. RLPs are decidable when a couple of natural assumptions are made: (i) satisﬁability of FO theories in the presence of closed predicates is decidable, and (ii) rules are safe in the style of the well-known DL-safeness. We further show that a large fragment of such RLPs can be translated into standard (disjunctive) ASP, for which efﬁcient implementations exist. For RLPs with theories expressed in DLs, we use a novel relaxation of safeness that safeguards rules via predicates whose extensions can be inferred to have a ﬁnite bound. We present several complexity results for the case where ontologies are written in some standard DLs.

PDF Details

AAAI Conference 2019 Conference Paper

Relaxing and Restraining Queries for OBDA

Medina Andreşel
Yazmín Ibáñez-García
Magdalena Ortiz
Mantas Šimkus

We advocate the use of ontologies for relaxing and restraining queries, so that they retrieve either more or less answers, enabling the exploration of a given dataset. We propose a set of rewriting rules to relax and restrain conjunctive queries (CQs) over datasets mediated by an ontology written in a dialect of DL-Lite with complex role inclusions (CRIs). The addition of CRI enables the representation of knowledge about data involving ordered hierarchies of categories, in the style of multi-dimensional data models. Although CRIs in general destroy the first-order rewritability of CQs, we identify settings in which CQs remain rewritable.

PDF Details

AAAI Conference 2018 Conference Paper

Combining Rules and Ontologies into Clopen Knowledge Bases

Labinot Bajraktari
Magdalena Ortiz
Mantas Šimkus

We propose Clopen Knowledge Bases (CKBs) as a new formalism combining Answer Set Programming (ASP) with ontology languages based on ﬁrst-order logic. CKBs generalize the prominent r-hybrid and DL+LOG languages of Rosati, and are more ﬂexible for speciﬁcation of problems that combine open-world and closed-world reasoning. We argue that the guarded negation fragment of ﬁrst-order logic (GNFO)—a very expressive fragment that subsumes many prominent ontology languages like Description Logics (DLs) and the guarded fragment—is an ontology language that can be used in CKBs while enjoying decidability for basic reasoning problems. We further show how CKBs can be used with expressive DLs of the ALC family, and obtain worst-case optimal complexity results in this setting. For DL-based CKBs, we deﬁne a fragment called separable CKBs (which still strictly subsumes r-hybrid and DL+LOG knowledge bases), and show that they can be rather efﬁciently translated into standard ASP programs. This approach allows us to perform basic inference from separable CKBs by reusing existing ef- ﬁcient ASP solvers. We have implemented the approach for separable CKBs containing ontologies in the DL ALCH, and present in this paper some promising empirical results for real-life data. They show that our approach provides a dramatic improvement over a naive implementation based on a translation of such CKBs into dl-programs.

PDF Details

IJCAI Conference 2013 Conference Paper

Conjunctive Regular Path Queries in Lightweight Description Logics

Meghyn Bienvenu
Magdalena Ortiz
Mantas Šimkus

Conjunctive regular path queries are an expressive extension of the well-known class of conjunctive queries and have been extensively studied in the database community. Somewhat surprisingly, there has been little work aimed at using such queries in the context of description logic (DL) knowledge bases, and all existing results target expressive DLs, even though lightweight DLs are considered better-suited for data-intensive applications. This paper aims to bridge this gap by providing algorithms and tight complexity bounds for answering two-way conjunctive regular path queries over DL knowledge bases formulated in lightweight DLs of the DL-Lite and EL families.

PDF Details DOI

IJCAI Conference 2013 Conference Paper

Tractable Queries for Lightweight Description Logics

Meghyn Bienvenu
Magdalena Ortiz
Mantas Šimkus
Guohui Xiao

It is a classic result in database theory that conjunctive query (CQ) answering, which is NP-complete in general, is feasible in polynomial time when restricted to acyclic queries. Subsequent results identified more general structural properties of CQs (like bounded treewidth) which ensure tractable query evaluation. In this paper, we lift these tractability results to knowledge bases formulated in the lightweight description logics DL-Lite and ELH. The proof exploits known properties of query matches in these logics and involves a querydependent modification of the data. To obtain a more practical approach, we propose a concrete polynomial-time algorithm for answering acyclic CQs based on rewriting queries into datalog programs. A preliminary evaluation suggests the interest of our approach for handling large acyclic CQs.

PDF Details DOI