A quest for new computer logics

Polish National Science Centre grant (OPUS 11, No. 2016/21/B/ST6/01444, 2017-2021)

Principal investigator: Emanuel Kieronski

The goal of the project is to investigate the decidability and the computational complexity of fragments of first-order logic mativated by computer science. Abstract of the project: [short.pdf].

Publications:

  • Emanuel Kieronski, Antti Kuusisto: One-Dimensional Fragment over Words and Trees. J. Log. Comput. 32(5): 902-941. 2022.
  • Emanuel Kieronski, Sebastian Rudolph: Finite model theory of the triguarded fragment and related logics (Extended Abstract). Description Logic 2021.
  • Emanuel Kieronski, Sebastian Rudolph: Finite model theory of the triguarded fragment and related logics. LICS 2021
  • Bartosz Bednarczyk, Emanuel Kieronski, Piotr Witkowski: Completing the Picture: Complexity of graded modal logics with converse. Theory Pract. Log. Program. 21(4): 493-520 (Selected JELIA'19 papers.) 2021
  • Bartosz Bednarczyk, Piotr Witkowski: A note on C2 interpreted over finite data-words. TIME 2020.
  • Emanuel Kieronski, Adam Malinowski: The Triguarded Fragment with Transitivity. LPAR 2020.
  • Emanuel Kieronski: One-Dimensional Guarded Fragments. MFCS 2019.
  • Daniel Danielski, Emanuel Kieronski: Finite Satisfiability of Unary Negation Fragment with Transitivity. MFCS 2019.
  • Jakub Michaliszyn, Piotr Witkowski: Decidability of Model Checking Multi-Agent Systems with Regular Expressions against Epistemic HS Specifications. IJCAI 2019.
  • Daniel Danielski, Emanuel Kieronski: Finite Satisfiability of Unary Negation Fragmentwith Transitivity (Extended Abstract). Description Logic 2019.
  • Bartosz Bednarczyk, Emanuel Kieronski, Piotr Witkowski: On the Complexity of Graded Modal Logics with Converse. JELIA 2019.
  • Witold Charatonik, Yegor Guskov, Ian Pratt-Hartmann, Piotr Witkowski: Two-variable First-Order Logic with Counting in Forests. LPAR 2018.
  • Lidia Tendera: Decidability Frontier for Fragments of First-Order Logic with Transitivity. Description Logics 2018.
  • Emanuel Kieronski, Ian Pratt-Hartmann, Lidia Tendera: Two-variable logics with counting and semantic constraints. SIGLOG News 5(3): 22-43 (2018)
  • Daniel Danielski, Emanuel Kieronski: Unary negation fragment with equivalence relations has the finite model property. LICS 2018.
  • Bartosz Bednarczyk, Witold Charatonik: Modulo Counting on Words and Trees. FSTTCS 2017.
  • Bartosz Bednarczyk, Witold Charatonik, Emanuel Kieronski: Extending Two-Variable Logic on Trees. CSL 2017.
  • Emanuel Kieronski, Antti Kuusisto: One-Dimensional Logic over Trees. MFCS 2017.
  • Bartosz Bednarczyk: On One Variable Fragment of First Order Logic with Modulo Counting Quantifier. ESSLLI 2017 Student Session.