Author name cluster

Lukas Gerlach

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.

5 papers

1 author row

KR Conference 2025 Conference Paper

About the Multi-Head Linear Restricted Chase Termination

Lukas Gerlach
Lucas Larroque
Jerzy Marcinkowski
Piotr Ostropolski-Nalewaja

The chase is a ubiquitous algorithm in database theory. However, for existential rules (aka tuple-generating dependencies), its termination is not guaranteed, and even undecidable in general. The problem of termination becomes particularly difficult for the restricted (or standard) chase, for which the order of rule application matters. Thus, decidability of restricted chase termination is still open for many well-behaved classes such as linear or guarded multi-headed rules. We make a step forward by showing that all-instances restricted chase termination is decidable in the linear multi-headed case.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Finite Groundings for ASP with Functions: A Journey through Consistency

Lukas Gerlach
David Carral
Markus Hecher

Answer set programming (ASP) is a logic programming formalism used in various areas of artificial intelligence like combinatorial problem solving and knowledge representation and reasoning. It is known that enhancing ASP with function symbols makes basic reasoning problems highly undecidable. However, even in simple cases, state of the art reasoners, specifically those relying on a ground-and-solve approach, fail to produce a result. Therefore, we reconsider consistency as a basic reasoning problem for ASP. We show reductions that give an intuition for the high level of undecidability. These insights allow for a more fine-grained analysis where we characterize ASP programs as "frugal" and "non-proliferous". For such programs, we are not only able to semi-decide consistency but we also propose a grounding procedure that yields finite groundings on more ASP programs with the concept of "forbidden" facts.

PDF Details DOI

KR Conference 2024 System Paper

Nemo: Your Friendly and Versatile Rule Reasoning Toolkit

Alex Ivliev
Lukas Gerlach
Simon Meusel
Jakob Steinberg
Markus Krötzsch

We present Nemo, a toolkit for rule-based reasoning and data processing that emphasises robustness and ease of use. Nemo’s core is a scalable and efficient main-memory reasoner that supports an expressive extension of Datalog with support for datatypes, existential rules, aggregates, and (stratified) negation. Built around this core is a versatile system of libraries and applications for interfacing with several data formats and programming languages, use as a progressive web application, and IDE integration. In this system description, we present this toolkit and discuss relevant application areas in rule-based knowledge representation, knowledge graph processing, and reasoner prototyping. Our evaluation on a range of tasks from these areas demonstrates Nemo’s robust performance in comparison to state-of-the-art rule engines.

PDF Details DOI

KR Conference 2023 Conference Paper

Do Repeat Yourself: Understanding Sufficient Conditions for Restricted Chase Non-Termination

Lukas Gerlach
David Carral

The disjunctive restricted chase is a sound and complete procedure for solving boolean conjunctive query entailment over knowledge bases of disjunctive existential rules. Alas, this procedure does not always terminate and checking if it does is undecidable. However, we can use acyclicity notions (sufficient conditions that imply termination) to effectively apply the chase in many real-world cases. To know if these conditions are as general as possible, we can use cyclicity notions (sufficient conditions that imply non-termination). In this paper, we discuss some issues with previously existing cyclicity notions, propose some novel notions for non-termination by dismantling the original idea, and empirically verify the generality of the new criteria.

PDF Details DOI

AAAI Conference 2023 Conference Paper

General Acyclicity and Cyclicity Notions for the Disjunctive Skolem Chase

Lukas Gerlach
David Carral

The disjunctive skolem chase is a sound, complete, and potentially non-terminating procedure for solving boolean conjunctive query entailment over knowledge bases of disjunctive existential rules. We develop novel acyclicity and cyclicity notions for this procedure; that is, we develop sufficient conditions to determine chase termination and non-termination. Our empirical evaluation shows that our novel notions are significantly more general than existing criteria.

PDF Details DOI