2 citations · 4 across the 7 of their papers we have counts for
8 papers
No Cliques Allowed: The Next Step Towards BDD/FC Conjecture
Lucas Larroque, Piotr Ostropolski-Nalewaja, Michaël Thomazo
This paper addresses one of the fundamental open questions in the realm of existential rules: the conjecture on the finite controllability of bounded derivation depth rule sets (bd…
The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules
Piotr Ostropolski-Nalewaja, Sebastian Rudolph
Extensive research in the field of ontology-based query answering has led to the identification of numerous fragments of existential rules (also known as tuple-generating dependenc…
Decidability of Quasi-Dense Modal Logics
Piotr Ostropolski-Nalewaja, Tim S. Lyon
The decidability of axiomatic extensions of the modal logic K with modal reduction principles, i.e. axioms of the form , has remained a l…
Connecting Proof Theory and Knowledge Representation: Sequent Calculi and the Chase with Existential Rules
Tim S. Lyon, Piotr Ostropolski-Nalewaja
Chase algorithms are indispensable in the domain of knowledge base querying, which enable the extraction of implicit knowledge from a given database via applications of rules from…
Decidability of Querying First-Order Theories via Countermodels of Finite Width
Thomas Feller, Tim S. Lyon, Piotr Ostropolski-Nalewaja +1
We propose a generic framework for establishing the decidability of a wide range of logical entailment problems (briefly called querying), based on the existence of countermodels t…
Foundations for an Abstract Proof Theory in the Context of Horn Rules
Tim S. Lyon, Piotr Ostropolski-Nalewaja
We introduce a novel, logic-independent framework for the study of sequent-style proof systems, which covers a number of proof-theoretic formalisms and concrete proof systems that…
Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying
Thomas Feller, Tim S. Lyon, Piotr Ostropolski-Nalewaja +1
In our pursuit of generic criteria for decidable ontology-based querying, we introduce 'finite-cliquewidth sets' (FCS) of existential rules, a model-theoretically defined class of…
A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem
Bartłomiej Dudek, Paweł Gawrychowski, Piotr Ostropolski-Nalewaja
In the Maximum Duo-Preservation String Mapping problem we are given two strings and wish to map the letters of the former to the letters of the latter so as to maximise the number…