Abstract: Conjunctive queries (CQs) are a core class of database queries, which support the operations join and projection. Direct access is the task of simulating a sorted array containing the query answers. That is, we want to construct a data structure that allows access calls that, given an index, return the answer in that index. As the number of query answers can be much larger than the input database, we want a construction time proportional to the input (and much smaller than the sorted array). We also want to be able to quickly update this data structure when records are modified. It is known for which queries this task can be done with only linear construction time and logarithmic update and access times, but we ask to know for which specific orders this is possible. We obtain a dichotomy that shows algorithms for q-hierarchical CQs with any topological order over its free variables and conditional lower bounds for the other CQs. Next, we plan to check how this result changes when the queries are enhanced with aggregates (such as counting, summation, average, and minimum). We hope to use an approach that computes aggregates by assigning records with elements from a commutative semiring.

Abstract: Determining if an input undirected graph is Hamiltonian, i.e., if it has a cycle that visits every vertex exactly once, is one of the most famous NP-complete problems. We consider the following generalization of Hamiltonian cycles: for a fixed set S of natural numbers, we want to visit each vertex of a graph G exactly once and ensure that any two consecutive vertices can be joined in k hops for some choice of k∈S. Formally, an S-Hamiltonian cycle is a permutation (v0,…,vn−1) of the vertices of G such that, for 0≤i≤n−1, there exists a walk between vi and vi+1modn whose length is in S. (We do not impose any constraints on how many times vertices can be visited as intermediate vertices of walks.) Of course Hamiltonian cycles in the standard sense correspond to S={1}. We study the S-Hamiltonian cycle problem of deciding whether an input graph G has an S-Hamiltonian cycle. Our goal is to determine the complexity of this problem depending on the fixed set S. It is already known that the problem remains NP-complete for S={1,2}, whereas it is trivial for S={1,2,3} because any connected graph contains a {1,2,3}-Hamiltonian cycle. Our work classifies the complexity of this problem for most kinds of sets S, with the key new results being the following: we have NP-completeness for S={2} and for S={2,4}, but tractability for S={1,2,4}, for S={2,4,6}, for any superset of these two tractable cases, and for S the infinite set of all odd integers. The remaining open cases are the non-singleton finite sets of odd integers, in particular S={1,3}. Beyond cycles, we also discuss the complexity of finding S-Hamiltonian paths, and show that our problems are all tractable on graphs of bounded cliquewidth. This work will be presented at WG’26.

Abstract: This is a rehearsal of the GT SISE presentation on Loup’s PhD topic.

Abstract: This is a rehearsal of the GT SISE presentation on Sébastien’s PhD topic.

Abstract: This is a rehearsal of the GT SISE presentation on Arthur’s PhD topic.

Abstract: It is known that the two-variable fragment FO2 of first-order logic remains decidable if it is completed with two equivalence relations, but becomes undecidable with three. In this work, we investigate the extension of FO2 with a nested family of equivalence relations E1 ⊆ E2 ⊆ E3 ⊆ … In particular, we show that even with a arbitrary long such chain, the logic remains decidable and with the same complexity (NExpTime). We also discuss other extensions (nested equivalence relations + one linear order, nested partial orders…), and the limitations of this result. This is a joint work with Oskar Fiuk and Emanuel Kieroński, from Wrocław.

Abstract: Neurosymbolic artificial intelligence is a growing field of research aiming to combine neural network learning capabilities with the reasoning abilities of symbolic systems.In the context of multi-label classification, prior knowledge about output labels can be expressed as a propositional formula whose models correspond to valid labelsets. This prior knowledge can then be integrated in a deep learning classifier in order to increase its performance, improve its training, constrain its outputs or provide explanations to the user. In this seminar, I will review several knowledge integration techniques based on probabilistic reasoning. I will analyze with a few experimental results how performance gains due to knowlege integration evolves with the scale of the underlying deep neural network. I will discuss the computational complexity of several probabilistic reasoning problems on which these techniques internally rely. Finally, I will sketch several avenues for future research, in particular on knowledge integration in multi-label conformal classification.

Abstract: We explore the fine-grained structure of classes of regular languages maintainable in fragments of first-order logic within the dynamic descriptive complexity framework of Patnaik and Immerman. A result by Hesse states that the class of regular languages is maintainable by first-order formulas even if only unary auxiliary relations can be used. Another result by Gelade, Marquardt, and Schwentick states that the class of regular languages coincides with the class of languages maintainable by quantifier-free formulas with binary auxiliary relations. We refine Hesse’s result and show that with unary auxiliary data ∃^∀^-formulas can maintain all regular languages. We then obtain precise algebraic characterizations of the classes of languages maintainable with quantifier-free formulas and positive ∃^*-formulas in the presence of unary auxiliary relations. This is joint work with Felix Tschirbs, Nils Vortmeier and Thomas Zeume.

Abstract: We show a theorem on monadic second-order k-ary queries on finite words. It may be illustrated by the following example: if the number of results of a query on binary strings is O(number of 0s \(\times\) number of 1s), then each result can be MSO-definably identified from a 0-position, a 1-position and some finite data. Joint work with Paweł Parys (University of Warsaw)

Abstract: Stream Reasoning is an emerging research area focused on deriving timely and actionable insights from high-velocity, continuously evolving data. It sits at the intersection of Artificial Intelligence and Stream Processing, with strong foundations in Knowledge Representation and Reasoning. Applications span domains such as the Internet of Things, real-time monitoring, social media analytics, and financial event processing. In this talk, I will introduce our work on RDF Stream Processing, a subfield of Stream Reasoning which connects Semantic Web with stream processing technologies. I will present current research activities at the Stream Intelligence Lab (KU Leuven, Campus Kortrijk), including our new reasoning engine, Kolibrie, designed for expressive and efficient reasoning over data streams. I will also discuss ongoing challenges and research directions such as managing inconsistency, incremental materialization, and reasoning on dynamic knowledge graphs.

A knowledge base is a database together with an ontology, which contains rules that can be used to infer new facts not explicitly present in the data. In the general case, this fact-generating procedure can run forever, creating infinitely many versions of the original database of possibly infinite size. When answering queries, all these possible worlds must be considered when computing the result. This version of query answering is called “query entailment”. More formally, we say that a query is entailed by a database if it is true in all of its extensions. To bring query entailment closer to database theory-style query answering, where the data is always finite, a finite version of query entailment has been considered for many classes of queries and rule languages. In the context of “finite query entailment”, a query is said to be entailed by a database if it is true in all of its finite extensions. Unfortunately, this finite semantics can lead to a loss of intended meaning, creating nonsensical databases that do not correspond to the user’s intuition. In this talk, I will introduce a new partially finite semantics, and its corresponding “partially finite query entailment” problem, that aims to reduce the disparity described above by allowing users to choose which part of the data must remain finite. I will show how the problem differs from its unrestricted and finite variants, and that it does not cause an increase in computational complexity, for the logic S. The talk will contain an introduction to the query entailment formalism and should be accessible to those without a background in Description Logics/Knowledge representation.

In this talk, we consider the task of representing the set of all homomorphisms between two finite relational structures by tractable circuit classes from knowledge compilation. The idea is that this may allow us to greatly compress the set, while still allowing us to perform various algorithmic tasks — such as counting and enumeration — efficiently. This is a very general problem which can alternatively be viewed as representing the answers to a CSP or as the result of a full conjunctive query on a relational database. Because of this the problem is in general intractable, we are interested in which restrictions of the problem become tractable. In particular, we are interested in left-hand-side restrictions: for which classes of structures C, is it the case that for every A in C and every B, the set of homomorphisms from A to B has a ‘small’ tractable circuit. I will discuss various results related to this problem. The talk is based on joint work with Christoph Berkholz.

Abstract: In Complex Event Processing (CEP), queries are evaluated over sequential data to recognize specific event patterns. Core features of CEP query languages include sequencing and correlation, the latter being closely related to join operations in relational databases. By slightly shifting perspective, evaluating a join query over sequential (i.e., time-ordered) data can be seen as query evaluation under updates, - a topic studied both in the Database Systems community (under Incremental View Maintenance, or IVM) and in the Database Theory community (under conjunctive queries with updates). In this talk, we’ll explore the connections between CEP, IVM, and conjunctive queries with updates. Building on these links, I’ll introduce a new query model: Conjunctive Queries with Insertion Order (CQ+IO) — a natural extension of conjunctive queries to event streams. This model lies at the intersection of CEP, IVM, and database theory. We investigate the expressive power of CQ+IO by characterizing the class of CQ+IO that can be translated into the automata model proposed for CEP by Pinto et al. (2025), and the class of CQ+IO that can be evaluated using the General Dynamic Yannakakis framework developed by Idris et al. (2020). Interestingly, these two classes intersect — laying the groundwork for transferring ideas and techniques between these previously separate fields.

This talk aims to advertise a new method for factorising words with respect to a finite monoid. The approach lets us represent a word as a tree of bounded size relative to the monoid, where long sequences of contiguous factors that induce the same effect in the monoid are abstracted by retaining only the first and last few. In the case of transition monoids, the size of this tree is polynomially bounded in terms of the size of the monoid. We will explore three a priori unrelated problems and show how they are connected to one another and to the short-ends factorisation method. The talk will focus on presenting those connections rather than describing the solutions. The first problem concerns the parameterised control of populations of MDPs. The second is the sequential flow problem, which asks whether it is possible to compose sequences of graph fragments in order to generate graphs with unbounded flow. The third problem is the computation of the subword closure of the language generated by an indexed grammar. For each of these problems, we establish optimal bounds.