An excursion to the border of decidability:
between two- and three-variable logic.
[pdf].
Co-author: Oskar Fiuk. Preprint.
2022
One-Dimensional Logic over Words and Trees.
[open access].
Co-author: Antti Kuusisto. Journal of Logic and Computation (online first).
Finite-Entailment of Local Queries in the Z family of Description Logics.
Co-author: Bartosz Bednarczyk. AAAI 2022. (An earlier version of this paper was presented also at Description Logic Workshop 2021.)
2021
Completing the Picture: Complexity of Graded Modal Logics with Converse.
[open access].
Co-authors: Bartosz Bednarczyk and Piotr Witkowski.
Theory and Practice of Logic Programming vol 21 Issue 4, 2021 (Special Issue from JELIA 2019).
Extended version of JELIA 2019 paper.
Finite Model Theory of the Triguarded Fragment and Related Logics.
Co-author: Sebastian Rudolph.
LICS 2021. For a slightly extended version see [arXiv]. Presented also at Description Logic Workshop 2021 and Highlights of Logic, Games and Automata 2021
2020
The Triguarded Fragment with Transitivity.
Co-author: Adam Malinowski. LPAR 2020. Proceedings, EPiC Series in Computing 73, pp. 334--353.
2019
One-Dimensional Guarded Fragments.
MFCS 2019. For full version see [arXiv].
Finite Satisfiability of Unary Negation Fragment with Transitivity.
Co-author: Daniel Danielski. MFCS 2019. For full version see [arXiv]. Presented also at Description Logic Workshop 2019.
On the Complexity of Graded Modal Logics with Converse.
Co-authors: Bartosz Bednarczyk, Piotr Witkowski. JELIA 2019. Proceedings, LNCS 11468, pp. 642-658.
For full version see [arXiv].
2018
Two-variable logics with counting and semantic constraints.
[ACM Author-Izer Service].
Co-authors: Ian Pratt-Hartmann, Lidia Tendera. SIGLOG News 5(3):22-43.
Unary negation fragment with equivalence relations has the finite model property.
[ACM Author-Izer Service].
Co-author: Daniel Danielski. LICS 2018.
Proceedings, pp. 285-294. An extended and improved version:
[arXiv].
Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants.
[ACM Author-Izer Service].
Co-author: Lidia Tendera. ACM Transactions on Computational Logic, Volume 19, Issue 2, Article No. 8 (34 pages). Extended version of LPAR 2007 paper.
[arXiv].
2017
One-Dimensional Logic over Trees.
[LIPIcs].
Co-author: Antti Kuusisto. MFCS 2017. Proceedings, LIPIcs 83, pp. 64:1--64:13.
Extending Two-Variable Logic on Trees.
[LIPIcs].
Co-authors: Bartosz Bednarczyk, Witold Charatonik. CSL 2017. Proceedings, LIPIcs 82, pp. 11:1--11:20.
A version containing some missing proofs:
[arXiv].
Equivalence Closure in the Two-Variable Guarded Fragment.
[JLC]
Co-authors: Ian Pratt-Hartmann and Lidia Tendera.
Journal of Logic and Computation, 27 (4): 999-1021.
2016
Complexity of Two-Variable Logic on Finite Trees.
[ACM Author-Izer Service].
Co-authors: Saguy Benaim, Michael Benedikt, Witold Charatonik,
Rastislav Lenhardt, Filip Mazowiecki, James Worrell. ACM Transactions on Computational Logic,
Volume 17, Issue 4, Article No. 32 (38 pages). Full version of ICALP 2013 paper.
One-Dimensional Logic over Words.
[LIPIcs].
CSL 2016. Proceedings, LIPIcs 62, pp. 38:1--38:15.
2015
On the Decidability of Elementary Modal Logics[ACM Author-Izer Service]. Co-authors: Jakub Michaliszyn, Jan Otop. ACM Transactions on Computational Logic,
Volume 17, Issue 1, Article No. 2 (47 pages). Full version of FSTTCS 2011, AIML 2012 papers and Michaliszyn and Otop's LICS 2012 paper.
Uniform One-Dimensional Fragments with one
Equivalence Relation.
[LIPIcs].
Co-author: Antti Kuusisto. CSL 2015. Proceedings, LIPIcs 41, pp. 597-615.
2014
Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality.
(full version: [arXiv]).
Co-author: Antti Kuusisto. MFCS 2014. Proceedings, Part I, LNCS 8634, pp. 365--376.
Decidability of Weak Logics with Deterministic Transitive Closure.
[ACM Author-Izer Service].
Co-authors: Witold Charatonik, Filip Mazowiecki.
CSL-LICS 2014. Proceedings, pp. 29:1--29:10.
Two-variable First-order Logic with Equivalence Closure.
[SIAM].
Co-authors: Jakub Michaliszyn, Ian Pratt-Hartmann, Lidia Tendera.
SIAM Journal on Computing, Volume 43, Issue 3, 2014, pp. 1012--1063. Journal version of LICS 2012 paper.
2013
Complexity of Two-Variable Logic on Finite Trees. Co-authors: Saguy Benaim, Michael Benedikt, Witold Charatonik,
Rastislav Lenhardt, Filip Mazowiecki, James Worrell. ICALP 2013. Proceedings, LNCS 7966, pp. 74-88. See also
journal version (2016)
Satisfiability of the Two-Variable Fragment of First-Order Logic Over Trees.
[arXiv] Co-authors: Witold Charatonik, Filip Mazowiecki. See also ICALP 2013 paper.
2012
Small Substructures and Decidability Issues for First-Order Logic with Two Variables.
[Euclid].
Co-author: Martin Otto. Journal of Symbolic Logic Volume 77, Issue 3 (2012), pp. 729-765.
Journal version of LICS 2005 paper.
Two-Variable Universal Logic with Transitive Closure.
[LIPIcs].
(version with appendix: [pdf]).
Co-author: Jakub Michaliszyn. CSL 2012. Proceedings, LIPIcs 16, pp. 396-410.
Finite Satisfiability of Modal Logic over Horn Definable Classes of Frames.
[pdf].
Co-author: Jakub Michaliszyn. AIML 2012. Proceedings, pp. 464-482. See also journal version (2015).
Two-Variable First-Order Logic with Equivalence Closure.
[pdf].
Co-authors: Jakub Michaliszyn, Ian Pratt-Hartmann, Lidia Tendera.
LICS 2012. Proceedings, pp. 431-440. See also journal version (2014).
2011
Modal Logics Definable by Universal Three-Variable Formulas. Co-authors: Jakub Michaliszyn, Jan Otop.
[LIPIcs].
FSTTCS 2011. Proceedings, LIPIcs 13, pp. 264--275. See also journal version (2015).
Decidability Issues for Two-Variable Logics with Several Linear Orders.
[LIPIcs].
CSL 2011. Proceedings, LIPIcs 12, pp. 337-351.
2010
B and D are enough to make the Halpern-Shoham logic undecidable. [pdf].
Co-authors:Jerzy Marcinkowski, Jakub Michaliszyn. ICALP 2010. Proceedings, LNCS 6199, pp. 357-368.
2009
On Finite Satisfiability of Two-Variable First-Order Logic with Equivalence Relations.
[ps].
Co-author: Lidia Tendera. LICS 2009. Proceedings, pp. 123-132.
2007
On Finite Satisfiability of the Guarded Fragment with Equivalence or Transitive Guards[ps].
Co-author: Lidia Tendera. LPAR 2007.
Proceedings, LNAI 4790, pp. 318-332.
2006
On the Complexity of the Two-Variable Guarded Fragment with Transitive Guards.
Information and Computation 204, pp. 1663-1703, 2006. Journal version of STACS 2002 and FOSSACS 2003 papers.
2005
Results on the Guarded Fragment with Equivalence or Transitive Relations[ps].
CSL 2005. Proceedings, LNCS 3634, pp. 309-324.
Small Substructures and Decidability Issues for First-Order Logic with Two Variables[ps]
Co-author: Martin Otto. LISC 2005. Proceedings, pp. 448-457. See also journal version (2012).
2003
The Two-Variable Guarded Fragment with Transitive Guards is 2ExpTime-Hard[ps].
FOSSACS 2003. Proceedings, LNCS 2620, pp. 299-312.
See also journal version (2006).
2002
ExpSpace-Complete Variant of Guarded Fragment with Transitivity[ps].
STACS 2002. Proceedings, LNCS 2285, pp. 608-619. See also journal vesrion (2006).