Publications of Bartosz Bednarczyk

Journal Articles

Bartosz Bednarczyk
Exploring Non-Regular Extensions of Propositional Dynamic Logic with Description-Logics Features.
Logical Methods in Computer Science, 20(2):7:1–7:31, May 2024
Details Download

Bartosz Bednarczyk, Stéphane Demri, Raul Fervari, Alessio Mansutti
On Composing Finite Forests with Modal Logics
ACM Transactions on Computational Logic, 24(2), April 2023
Details Download

Bartosz Bednarczyk, Sebastian Rudolph
How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC
Journal of Artificial Intelligence Research, 78:385–458, November 2023
Details Download

Bartosz Bednarczyk, Stéphane Demri
Why Does Propositional Quantification Make Modal and Temporal Logics on Trees Robustly Hard?
Logical Methods in Computer Science, Volume 18, Issue 3(5), July 2022
Details Download

Bartosz Bednarczyk
Statistical EL is ExpTime-complete
Information Processing Letters, 169C(106113), August 2021
Details Download

Bartosz Bednarczyk, Emanuel Kieroński, Piotr Witkowski
Completing the Picture: Complexity of Graded Modal Logics with Converse
Theory and Practice of Logic Programming, 21(4):493--520, April 2021
Details Download

Bartosz Bednarczyk
One-Variable Logic Meets Presburger Arithmetic
Theoretical Computer Science, 802(141-146), January 2020
Details Download

Proceedings Articles

Bartosz Bednarczyk
Data Complexity in Expressive Description Logics With Path Expressions
Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024, 3241--3249, August 2024. ijcai.org
Details Download

Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann
On the Limits of Decision: the Adjacent Fragment of First-Order Logic
In Kousha Etessami, Uriel Feige, and Gabriele Puppis, eds., Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming, ICALP 2023, volume 261 of Leibniz International Proceedings in Informatics, 114:1--114:20, to appear. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Details Download

Bartosz Bednarczyk
Beyond ALCreg: Exploring Non-Regular Extensions of PDL with Description Logics Features
In Sarah Alice Gaggl, Maria Vanina Martinez, Magdalena Ortiz, eds., Proceedings of the 18th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2023), Logics in Artificial Intelligence, 289--305, to appear. Springer International Publishing
Details Download

Bartosz Bednarczyk, Reijo Jaakkola
Towards Model Theory of Ordered Logics: Expressivity and Interpolation
In Stefan Szeider, Robert Ganian, Alexandra Silva, eds., Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), volume 241 of Leibniz International Proceedings in Informatics, 15:1--15:14, August 2022. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Details Download

Bartosz Bednarczyk, Oskar Fiuk
Presburger Büchi Tree Automata with Applications to Logics with Expressive Counting
In Agata Ciabattoni, Elaine Pimentel, Ruy J. G. B. de Queiroz, eds., Proceedings of the 28th Workshop on Logic, Language, Information and Computation (WOLLIC 2022), volume 2022 of Logic, Language, Information, and Computation, 295--308, September 2022. Springer International Publishing
Details Download

Bartosz Bednarczyk, Sebastian Rudolph
The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2EXPTIME-hard
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), 5495-5502, February 2022
Details Download

Bartosz Bednarczyk, Emanuel Kieroński
Finite Entailment of Local Queries in the Z family of Description Logics
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), volume 36, 5487--5494, February 2022. AAAI Press
Details Download

Bartosz Bednarczyk, Mateusz Urbanczyk
Comonadic Semantics for Description Logics Games
In Ofer Arieli, Martin Homola, Jean Christoph Jung, Marie-Laure Mugnier, eds., Proceedings of the 35th International Workshop on Description Logics (DL 2022), August 2022
Details Download

Bartosz Bednarczyk, Emanuel Kieroński
Finite-Controllability of Conjunctive Queries in the Z family of Description Logics (Extended Abstract)
In Martin Homola, Vladislav Ryzhikov, Renate A. Schmidt, eds., Proceedings of the 34th International Workshop on Description Logics (DL 2021), volume 2954 of CEUR Workshop Proceedings, September 2021. CEUR-WS.org
Details Download

Bartosz Bednarczyk, Maja Orłowska, Anna Pacanowska, Tony Tan
On Classical Decidable Logics extended with Percentage Quantifiers and Arithmetics
In Mikołaj Bojańczyk, Chandra Chekuri, eds., Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), volume 213 of Leibniz International Proceedings in Informatics, 36:1--36:15, December 2021. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
Details Download

Bartosz Bednarczyk
Exploiting forwardness: Satisfiability and Query-Entailment in Forward Guarded Fragment
In Wolfgang Faber, Gerhard Friedrich, Martin Gebser, Michael Morak, eds., Proceedings of the 17th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2021), volume 12678 of Lecture Notes in Computer Science, 179--193, May 2021. Springer International Publishing
Details Download

Bartosz Bednarczyk, Jakub Michaliszyn
"Most of" leads to undecidability: Failure of adding frequencies to LTL
In Stefan Kiefer, Christine Tasson, eds., Proceedings of the Foundations of Software Science and Computation Structures - 24th International Conference (FOSSACS 2021), volume 12650 of Lecture Notes in Computer Science, 82--101, March 2021. Springer
Details Download

Bartosz Bednarczyk, Sebastian Rudolph
The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard (Extended Abstract)
In Martin Homola, Vladislav Ryzhikov, Renate A. Schmidt, eds., Proceedings of the 34th International Workshop on Description Logics (DL 2021), volume 2954 of CEUR Workshop Proceedings, September 2021. CEUR-WS.org
Details Download

Franz Baader, Bartosz Bednarczyk, Sebastian Rudolph
Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints
In Giuseppe De Giacomo. Alejandro Catala, Bistra Dilkina, Michela Milano, Senen Barro and Alberto Bugarin, Jerome Lang, eds., Proceedings of the 24th European Conference on Artificial Intelligence (ECAI 2020), volume 325 of Frontiers in Artificial Intelligence and Applications, 616-623, June 2020. IOS Press
Details Download

Bartosz Bednarczyk, Stéphane Demri, Alessio Mansutti
A Framework for Reasoning about Dynamic Axioms in Description Logics
In Christian Bessiere, eds., Proceedings of the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (IJCAI 2020), ijcai.org, 1681--1687, July 2020. International Joint Conferences on Artificial Intelligence
Details Download

Bartosz Bednarczyk, Stéphane Demri, Raul Fervari, Alessio Mansutti
Modal Logics with Composition on Finite Forests: Expressivity and Complexity
In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, Dale Miller, eds., Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2020), 167--180, June 2020. ACM
Details Download

Bartosz Bednarczyk, Piotr Witkowski
A note on C2 interpreted over finite data-words
In Emilio Muñoz-Velasco, Ana Ozaki, Martin Theobald, eds., Proceedings of the 27th International Symposium on Temporal Representation and Reasoning (TIME 2020), volume 178 of Leibniz International Proceedings in Informatics, 17:1--17:14, September 2020. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Details Download

Bartosz Bednarczyk, Robert Ferens, Piotr Ostropolski-Nalewaja
All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
In Christian Bessiere, eds., Proceedings of the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (IJCAI 2020), ijcai.org, 1719--1725, July 2020. International Joint Conferences on Artificial Intelligence
Details Download

Franz Baader, Bartosz Bednarczyk, Sebastian Rudolph
Satisfiability Checking and Conjunctive Query Answering in Description Logics with Global and Local Cardinality Constraints
In Mantas Simkus, Grant E. Weddell, eds., Proceedings of the 32nd International Workshop on Description Logics, volume 2373 of CEUR Workshop Proceedings, June 2019. CEUR-WS.org
Details Download

Bartosz Bednarczyk, Sebastian Rudolph
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
In Mantas Simkus, Grant E. Weddell, eds., Proceedings of the 32nd International Workshop on Description Logics, volume 2373 of CEUR Workshop Proceedings, June 2019. CEUR-WS.org
Details Download

Bartosz Bednarczyk, Stéphane Demri
Why propositional quantification makes modal logics on trees robustly hard ?
Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019), 1--13, June 2019. IEEE
Details Download

Bartosz Bednarczyk, Sebastian Rudolph
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
In Sarit Kraus, eds., Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI 2019), ijcai.org, 1530--1536, August 2019. International Joint Conferences on Artificial Intelligence
Details Download

Bartosz Bednarczyk, Emanuel Kieroński, Piotr Witkowski
On the Complexity of Graded Modal Logics with Converse.
In Francesco Calimeri, Nicola Leone, Marco Manna, eds., Proceedings of Logics in Artificial Intelligence - 16th European Conference (JELIA 2019), volume 11468 of LNCS, 642--658, May 2019. Lecture Notes in Computer Science
Details Download

Bartosz Bednarczyk, Witold Charatonik
Modulo Counting on Words and Trees.
In Satya V. Lokam, R. Ramanujam, eds., FSTTCS 2017, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, volume 93 of Leibniz International Proceedings in Informatics, 12:1--12:16, December 2017. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Details Download

Bartosz Bednarczyk, Witold Charatonik, Emanuel Kieroński
Extending Two-Variable Logic on Trees
In Valentin Goranko, Mads Dam, eds., Proceedings of 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), volume 82 of Leibniz International Proceedings in Informatics, 11:1--11:20, August 2017. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Details Download

Doctoral Theses

Bartosz Bednarczyk
Database-Inspired Reasoning Problems in Description Logics With Path Expressions
Phd thesis, Technischen Universitat Dresden, 2024/06/25
Details Download

Technical Reports

Bartosz Bednarczyk
Lutz's Spoiler Technique Revisited: A Unified Approach to Worst-Case Optimal Entailment of Unions of Conjunctive Queries in Locally-Forward Description Logics
Technical Report, arXiv.org, August 2021. Technical Report
Details Download

Franz Baader, Bartosz Bednarczyk, Sebastian Rudolph
Satisfiability Checking and Conjunctive Query Answering in Description Logics with Global and Local Cardinality Constraints
Technical Report, Computational Logic Group, 2019
Details Download