Institute of Computer Science
Office hours: Tuesday 9.15-10.00, Thursday 12.15-13.15 |

- Decidability and complexity of decision problems in logic
- Two-variable logics and guarded fragments

- Preprints
. Co-author: Daniel Danielski. [arXiv].*Unary negation fragment with equivalence relations has the finite model property*

- 2018
. Co-author: Lidia Tendera. ACM Transactions on Computational Logic, Volume 19, Issue 2, Article No. 8 (34 pages). Full version of LPAR 2007 paper. [arXiv].*Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants*

- 2017
. [LIPIcs]. Co-author: Antti Kuusisto. MFCS 2017. Aalborg, Denmark. Proceedings, LIPIcs 83, pp. 64:1--64:13.*One-Dimensional Logic over Trees*. [LIPIcs]. Co-authors: Bartosz Bednarczyk, Witold Charatonik. CSL 2017. Stockholm, Sweden. Proceedings, LIPIcs 82, pp. 11:1--11:20. A version containing some missing proofs: [arXiv].*Extending Two-Variable Logic on Trees*. [JLC] Co-authors: Ian Pratt-Hartmann and Lidia Tendera. Journal of Logic and Computation, 27 (4): 999-1021.*Equivalence Closure in the Two-Variable Guarded Fragment*

- 2016
. [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.*Complexity of Two-Variable Logic on Finite Trees*. [LIPIcs]. CSL 2016. Marseille, France, August 29 - September 1. Proceedings, LIPIcs 62, pp. 38:1--38:15.*One-Dimensional Logic over Words*

- 2015
[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.*On the Decidability of Elementary Modal Logics*. [LIPIcs]. Co-author: Antti Kuusisto. CSL 2015. Berlin, Germany, September 6-10, 2015. Proceedings, LIPIcs 41, pp. 597-615.*Uniform One-Dimensional Fragments with one Equivalence Relation*

- 2014
. (full version: [arXiv]). Co-author: Antti Kuusisto. MFCS 2014. Budapest, Hungary, August 26-29, 2014. Proceedings, Part I, LNCS 8634, pp. 365--376.*Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality*. [ACM Author-Izer Service]. Co-authors: Witold Charatonik, Filip Mazowiecki. CSL-LICS 2014. Vienna, Austria, July 14 - 18, 2014. Proceedings, pp. 29:1--29:10.*Decidability of Weak Logics with Deterministic Transitive 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.*Two-variable First-order Logic with Equivalence Closure*

- 2013
. Co-authors: Saguy Benaim, Michael Benedikt, Witold Charatonik, Rastislav Lenhardt, Filip Mazowiecki, James Worrell. ICALP 2013. Riga, Latvia, July 8-12, 2013. Proceedings, LNCS 7966, pp. 74-88. See also journal version (2016)*Complexity of Two-Variable Logic on Finite Trees*. [arXiv] Co-authors: Witold Charatonik, Filip Mazowiecki. See also ICALP 2013 paper.*Satisfiability of the Two-Variable Fragment of First-Order Logic Over Trees*

- 2012
. [Euclid]. Co-author: Martin Otto. Journal of Symbolic Logic Volume 77, Issue 3 (2012), pp. 729-765. Journal version of LICS 2005 paper.*Small Substructures and Decidability Issues for First-Order Logic with Two Variables*. [LIPIcs]. (version with appendix: [pdf]). Co-author: Jakub Michaliszyn. CSL 2012. Fontainebleau, France, September 3-6, 2012. Proceedings, LIPIcs 16, pp. 396-410.*Two-Variable Universal Logic with Transitive Closure*. [pdf]. Co-author: Jakub Michaliszyn. AIML 2012. Copenhagen, Denmark, August 25-28, 2012. Proceedings, pp. 464-482. See also journal version (2015).*Finite Satisfiability of Modal Logic over Horn Definable Classes of Frames*. [pdf]. Co-authors: Jakub Michaliszyn, Ian Pratt-Hartmann, Lidia Tendera. LICS 2012. Dubrovnik, Croatia, June 25-28, 2012. Proceedings, pp. 431-440. See also journal version (2014).*Two-Variable First-Order Logic with Equivalence Closure*

- 2011
. Co-authors: Jakub Michaliszyn, Jan Otop. [LIPIcs]. FSTTCS 2011. Mumbai, India, December 12-14, 2011. Proceedings, LIPIcs 13, pp. 264--275. See also journal version (2015).*Modal Logics Definable by Universal Three-Variable Formulas*. [LIPIcs]. CSL 2011. Bergen, Norway, September 11-15, 2011. Proceedings, LIPIcs 12, pp. 337-351.*Decidability Issues for Two-Variable Logics with Several Linear Orders*

- 2010
. [pdf]. Co-authors:Jerzy Marcinkowski, Jakub Michaliszyn. ICALP 2010. Bordeaux, France, July 5-10, 2010. Proceedings, LNCS 6199, pp. 357-368.*B and D are enough to make the Halpern-Shoham logic undecidable*

- 2009
. [ps]. Co-author: Lidia Tendera. LICS 2009. Los Angeles, USA, August 11-14, 2009. Proceedings, pp. 123-132.*On Finite Satisfiability of Two-Variable First-Order Logic with Equivalence Relations*

- 2007
[ps]. Co-author: Lidia Tendera. LPAR 2007. Yerevan, Armenia, October 15-19, 2007. Proceedings, LNAI 4790, pp. 318-332.*On Finite Satisfiability of the Guarded Fragment with Equivalence or Transitive Guards*

- 2006
. Information and Computation 204, pp. 1663-1703, 2006. Journal version of STACS 2002 and FOSSACS 2003 papers.*On the Complexity of the Two-Variable Guarded Fragment with Transitive Guards*

- 2005
[ps]. CSL 2005. Oxford, England, August 22-25, 2005. Proceedings, LNCS 3634, pp. 309-324.*Results on the Guarded Fragment with Equivalence or Transitive Relations*[ps] Co-author: Martin Otto. LISC 2005. Chicago, USA, June 26-29, 2005. Proceedings, pp. 448-457. See also journal version (2012).*Small Substructures and Decidability Issues for First-Order Logic with Two Variables*

- 2003
[ps]. FOSSACS 2003. Warsaw, Poland, April 7-11. Proceedings, LNCS 2620, pp. 299-312. See also journal version (2006).*The Two-Variable Guarded Fragment with Transitive Guards is 2ExpTime-Hard*

- 2002
[ps]. STACS 2002, Antibes - Juan les Pins, France, March 14-16, 2002. Proceedings, LNCS 2285, pp. 608-619. See also journal vesrion (2006).*ExpSpace-Complete Variant of Guarded Fragment with Transitivity*