Automatic reasoning about specifications in simple logics - decidability and complexity issues

2013/09/B/ST6/01535

Keywords

Descriptors

  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
  • ST6_10: Technologie i systemy informatyczne, bazy danych, technologie internetowe w tym wyszukiwanie informacji i biblioteki cyfrowe

Panel

ST6 – Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution

Uniwersytet Opolski

Voivodeship: opolskie

Other projects carried out by the institution »

Principal investigator (from the host institution)

dr hab. Lidia Zofia Tendera

Number of co-investigators in the project: 4

Call

OPUS 5 – announced on 2013-03-15

Amount awarded
672 512 PLN
Project start date
2014-03-11
Project end date
2018-03-10
Project duration
48 months (the same as in the proposal)
Project status
Project settled

Equipment purchased [PL]

  1. Notebook lub laptop (4 pcs). Cost: 30 000 PLN

Information in the final report

Publication in academic press/journals (8)

  1. Equivalence closure in the two-variable guarded fragment

    Authors:
    Emanuel Kieroński, Ian Pratt-Hartmann, Lidia Tendera
    Academic press:
    Journal of Logic and Computation (year: 2017, volume: nie dotyczy, pages: 999-1021), Publisher: Oxford University Press
    Status:
    Published
    DOI:
    10.1093/logcom/exv075 – link to the publication
  2. Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants

    Authors:
    Emanuel Kieroński, Lidia Tendera
    Academic press:
    ACM Transactions on Computational Logic (year: 2018, volume: 19 (2), pages: No. 8), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/3174805 – link to the publication
  3. Quine's Fluted Fragment Revisited

    Authors:
    Ian Pratt-Hartmann, Wiesław Szwast, Lidia Tendera
    Academic press:
    The Journal of Symbolic Logic (year: 2019, volume: 84 (3), pages: 1020-1048), Publisher: Cambridge University Press
    Status:
    Published
    DOI:
    10.1017/jsl.2019.33 – link to the publication
  4. On the satisfiability problem for fragments of the two-variable logic with one transitive relation

    Authors:
    Wiesław Szwast, Lidia Tendera
    Academic press:
    Journal of Logic and Computation (year: 2019, volume: online, pages: brak), Publisher: Oxford University Press
    Status:
    Published
    DOI:
    10.1093/logcom/exz012 – link to the publication
  5. Converging to the chase– A tool for finite controllability

    Authors:
    Tomasz Gogacz, Jerzy Marcinkowski
    Academic press:
    Journal of Computer and System Sciences (year: 2017, volume: 83, pages: 180-206), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2016.08.001 – link to the publication
  6. Two-variable first-order logic with equivalence closure

    Authors:
    Emanuel Kieroński, Jakub Michaliszyn, Ian Pratt-Hartmann, Lidia Tendera
    Academic press:
    SIAM Journal on Computing (year: 2014, volume: 43, pages: 1012-1063), Publisher: SIAM
    Status:
    Published
    DOI:
    10.1137/120900095 – link to the publication
  7. Complexity of Two-Variable Logic on Finite Trees

    Authors:
    Saguy Benaim, Michael Benedikt, Witold Charatonik, Emanuel Kieroński, Rastislav Lenhardt, Filip Mazowiecki, and James Worrell.
    Academic press:
    ACM Transactions on Computational Logic (year: 2016, volume: 17, pages: 32:1--32:38), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/2996796 – link to the publication
  8. On the Decidability of Elementary Modal Logics

    Authors:
    Jakub Michaliszyn, Jan Otop, Emanuel Kieroński
    Academic press:
    ACM Transactions on Computational Logic (year: 2015, volume: 17, Issue 1, pages: 2:1--2:47), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/2817825 – link to the publication

Articles in post-conference publications (10)

  1. All-instances termination of chase is undecidable

    Authors:
    Tomasz Gogacz, Jerzy Marcinkowski
    Conference:
    Automata, Languages, and Programming: 41st International Colloquium, ICALP (year: 2014, pages: 293-304), Publisher: Springer
    Date:
    conference July 8-11, 2014
    Status:
    Published
  2. Decidability of weak logics with deterministic transitive closure

    Authors:
    Witold Charatonik, Emanuel Kieroński, Filip Mazowiecki
    Conference:
    CSL-LICS '14: Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (year: 2014, pages: 29:1--29:10), Publisher: ACM
    Date:
    conference July 14 - 18, 2014
    Status:
    Published
  3. Quine's Fluted Fragment is Non-Elementary

    Authors:
    Ian Pratt-Hartmann, Wiesław Szwast, Lidia Tendera
    Conference:
    Computer Science Logic (year: 2016, pages: 39:1--39:21), Publisher: Leibniz International Proceedings in Informatics (LIPIcs)
    Date:
    conference August 29 - September 1
    Status:
    Published
    DOI:
    link to the publication
  4. Uniform One-Dimensional Fragments with one Equivalence Relation

    Authors:
    Emanuel Kieroński, Antti Kuusisto
    Conference:
    Computer Science Logic (year: 2015, pages: 597-615), Publisher: Leibniz International Proceedings in Informatics (LIPIcs)
    Date:
    conference 7-10 September
    Status:
    Published
    DOI:
    link to the publication
  5. Complexity and expressivity of uniform one-dimensional fragment with equality

    Authors:
    Emanuel Kieroński, Antti Kuusisto
    Conference:
    Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS (year: 2014, pages: 365-376), Publisher: Springer
    Date:
    conference August 26-29, 2014
    Status:
    Published
  6. Finite Model Reasoning in Expressive Fragments of First-Order Logic

    Authors:
    Lidia Tendera
    Conference:
    the Ninth Workshop on Methods for Modalities (M4M9 2017) (year: 2017, pages: 243: 43-57), Publisher: Open Publishing Association, EPTCS
    Date:
    conference 8-10 Jan 2017
    Status:
    Published
    DOI:
    link to the publication
  7. The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable

    Authors:
    Tomasz Gogacz, Jerzy Marcinkowski
    Conference:
    30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (year: 2015, pages: 281--292), Publisher: IEEE Computer Society Press
    Date:
    conference July 6-10 2015
    Status:
    Published
  8. Characterizing XML Twig Queries with Examples

    Authors:
    Sławomir Staworko, Piotr Wieczorek
    Conference:
    18th International Conference on Database Theory (ICDT) (year: 2015, pages: 144--160), Publisher: Leibniz International Proceedings in Informatics (LIPIcs)
    Date:
    conference March 23-27, 2015
    Status:
    Published
    DOI:
    link to the publication
  9. Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy is Undecidable

    Authors:
    Tomasz Gogacz, Jerzy Marcinkowski
    Conference:
    35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (year: 2016, pages: 121--134), Publisher: ACM
    Date:
    conference June 26 - July 01
    Status:
    Published
    DOI:
    link to the publication
  10. One-Dimensional Logic over Words

    Authors:
    Emanuel Kieroński
    Conference:
    Computer Science Logic (year: 2016, pages: 38:1--38:15), Publisher: Leibniz International Proceedings in Informatics (LIPIcs)
    Date:
    conference August 29 - September 1
    Status:
    Published
    DOI:
    link to the publication

« New search

Graphic design and implementation: Jakub Piotrowski