Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Knowledge Representation Seminar (20.11.2026)

Friday 20.11.2026 at 13:00, Lecture room I 9


18. 11. 2026 17.35 hod.
By: Júlia Pukancová

Janos Arpasi:
A Horn Extension of DL-Lite with NL Data Complexity 

The literature on ontology-mediated query answering (OMQA) has been shaped by two key results: first-order rewritability for DL-Lite, and PTime-hardness of data complexity for essentially every description logic beyond it. This has effectively positioned DL-Lite as the only practical choice for query rewriting, restricting OMQA solutions to first-order queries and ontologies that can be rewritten into them. This AC_0 vs. PTime dichotomy is especially limiting if we consider that OMQA targets graph-structured data, and that standard graph query languages (including the recent ISO standards GQL and SQL/PGQ) are typically NL-complete. Towards identifying a rich Horn DL that can be rewritten into graph query languages and that can still express many ℰℒℐ and DL-Lite ontologies, we introduce a stratification mechanism for ℰℒℐ that controls the interaction between conjunction and recursion. In this way, we obtain ℰℒℋℐ^⊥_⪯, a description logic that strictly extends the core DL-Lite, supports reachability axioms and restricted conjunction, and allows for reasoning in NL. We establish the NL upper bound via a rewriting into nested two-way regular path queries, a fragment of GQL, providing initial evidence that our ontology language is a promising candidate for extending OMQA to graph query languages.

 

Jonas Haldimann:
Towards Defeasible Reasoning about Actions and Their Effects
 

Intelligent agents interacting with their environment need to reason about the effects their actions will have on their surroundings. For actions with deterministic outcome this problem is well investigated in the context of planning problems. But many real-world actions may not always result in their typical outcome, and exceptional outcomes of an action have to be taken into account. In this work we present a framework for reasoning about actions with uncertain outcomes. Inspired by conditionals, we introduce defeasible action rules that capture the typical outcome of action, without committing to what happens in exceptional circumstances. For the semantics of these rules we introduce ranked transition schemas: graph-based representations of transitions between possible worlds in which edges between states are assigned a rank indicating their typicality. We define an inference operator for defeasible action rules inspired by rational closure, adapting its intuitive semantics to the dynamic setting. Furthermore, we explore a generalization of this framework that uses partial orderings over transitions instead of ranks. This generalization strictly increases expressive power and enables more refined reasoning operators. Finally, we extend the language of defeasible action rules with a notation to express that certain properties are not affected by the execution of an action, thus allowing to explicitly formulate frame axioms in this defeasible setting.
 

Anouk Oudshoorn:
Static Analysis of Recursive SHACL 

The Shape Constraint Language (SHACL) is one of the prominent W3C standards for managing Resource Description Framework (RDF) data, a graph-based data model of the web. Its purpose: to describe constraints on datasets. The main task of interest is validation of a given a set of constraints on a given graph, which ensures data quality. This talk focusses on recursive SHACL, and in particular on its reasoning services beyond validation: when is a SHACL document not contradicting itself? How does this SHACL document compare to that? How can we determine this?  

In the full language there are many aspects that make these problems, satisfiability and implication, undecidable. Therefore, we shift our focus to: for which fragments are concrete techniques known? Can we decide the precise complexity? Can we provide new techniques? We will look at these questions for multiple semantics considered for recursive SHACL: supported model, stable model and well-founded semantics, and the least-fixed point semantics for stratified constraints. We find that satisfiability of different fragments is surprisingly close to similar settings in Description Logics and closely related logics, whereas implication, in most logics equivalent to satisfiability, is not. Nevertheless, via fixed point logics, we still find a way to decidable fragments.