A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem. - Bartlomiej Dudek 001; Pawel Gawrychowski; Piotr Ostropolski-Nalewaja (CPM, 2017)

Can One Escape Red Chains?: Regular Path Queries Determinacy is Undecidable. - Grzegorz Gluch; Jerzy Marcinkowski; Piotr Ostropolski-Nalewaja (LICS, 2018)

The First Order Truth Behind Undecidability of Regular Path Queries Determinacy. - Grzegorz Gluch; Jerzy Marcinkowski; Piotr Ostropolski-Nalewaja (ICDT, 2019)

All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs. - Bartosz Bednarczyk; Robert Ferens; Piotr Ostropolski-Nalewaja (IJCAI, 2020)

Determinacy of Real Conjunctive Queries. The Boolean Case. - Jaroslaw Kwiecien; Jerzy Marcinkowski; Piotr Ostropolski-Nalewaja (PODS, 2022)

A Journey to the Frontiers of Query Rewritability. - Piotr Ostropolski-Nalewaja; Jerzy Marcinkowski; David Carral; Sebastian Rudolph (PODS, 2022)

Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying. - Thomas Feller 001; Tim S. Lyon; Piotr Ostropolski-Nalewaja; Sebastian Rudolph (ICDT, 2023)

Connecting Proof Theory and Knowledge Representation: Sequent Calculi and the Chase with Existential Rules. - Tim S. Lyon; Piotr Ostropolski-Nalewaja (KR, 2023)

Foundations for an Abstract Proof Theory in the Context of Horn Rules. - Tim S. Lyon; Piotr Ostropolski-Nalewaja (CoRR, 2023)

On Monotonic Determinacy and Rewritability for Recursive Queries and Views. - Michael Benedikt; Stanislav Kikot; Piotr Ostropolski-Nalewaja; Miguel Romero 001 (ACM Trans. Comput. Log., 2023)

Monotone Rewritability and the Analysis of Queries, Views, and Rules. - Michael Benedikt; Stanislav Kikot; Johannes Marti; Piotr Ostropolski-Nalewaja (KR, 2024)

The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules. - Piotr Ostropolski-Nalewaja; Sebastian Rudolph (KR, 2024)

Decidability of Quasi-Dense Modal Logics. - Tim S. Lyon; Piotr Ostropolski-Nalewaja (LICS, 2024)

Decidability of Querying First-Order Theories via Countermodels of Finite Width. - Thomas Feller 001; Tim S. Lyon; Piotr Ostropolski-Nalewaja; Sebastian Rudolph (Log. Methods Comput. Sci., 2025)

Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories. - Jerzy Marcinkowski; Piotr Ostropolski-Nalewaja (CoRR, 2025)

No Cliques Allowed: The Next Step Towards BDD/FC Conjecture. - Lucas Larroque; Piotr Ostropolski-Nalewaja; Michaël Thomazo (Proc. ACM Manag. Data, 2025)