Emanuel Kieronski's home page

Emanuel Kieroński

Institute of Computer Science
University of Wrocław
ul. Joliot-Curie 15, room 304
50-383 Wrocław

Phone: +48 71 375 78 21
Email: kiero [at] cs [dot] uni [dot] wroc [dot] pl

Office hours: Wednesday 10-12

Research interests

Logic in computer science.
In particular: decidability and complexity of fragments of first-order logic (two-variable logics, guarded fragments, modal and description logics, etc.)

Recent research projects

Polish National Science Centre grant 2016/21/B/ST6/01444: A quest for new computer logics. 2017-2021
Polish National Science Centre grant 2021/41/B/ST6/00996: From expressive description logics to multi-variable fragments of first-order logic: Reasoning in finite structures. 2022-2025

PC membership

ICALP 2017, AAAI 2020, ECAI 2020, AAAI 2021, ICALP 2021, AAAI 2022, CSL 2022, KR 2022, AAAI 2023, AAAI 2024

List of publications

(See also: [DBLP] [Google Scholar].)

2024
- On the Complexity of Maslov's class K̅. Co-authors: Oskar Fiuk, Vincent Michielini. Accepted for LICS 2024
- Alternating Quantifiers in Uniform One-Dimensional Fragments with an Excursion into Three-Variable Logic. Co-author: Oskar Fiuk. [arXiv]. Full version of GandALF 23 and LPAR 23 papers.
2023
- A Uniform One-Dimensional Fragment with Alternation of Quantifiers. [EasyChair]. GandALF 2023.
- An excursion to the border of decidability: between two- and three-variable logic. [EPiC]. Co-author: Oskar Fiuk. LPAR 2023.
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).