Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

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

2013/09/B/ST6/01535

Keywords:

computational logic computational complexity decidability satisfiability description logic two-variable logic

Descriptors:

  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • ST6_10: Web and information systems, database systems, internet technologies, including information retrieval and digital libraries

Panel:

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

Host institution :

Uniwersytet Opolski

woj. opolskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Lidia 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 (Y-m-d): 2014-03-11

Project end date (Y-m-d): 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 szt.) (30 000 PLN)

Information in the final report

  • Publication in academic press/journals (8)
  • Articles in post-conference publications (10)
  1. Quine's Fluted Fragment Revisited
    Authors:
    Ian Pratt-Hartmann, Wiesław Szwast, Lidia Tendera
    Academic press:
    The Journal of Symbolic Logic (rok: 2019, tom: 84 (3), strony: 1020-1048), Wydawca: Cambridge University Press
    Status:
    Published
    DOI:
    10.1017/jsl.2019.33 - link to the publication
  2. Equivalence closure in the two-variable guarded fragment
    Authors:
    Emanuel Kieroński, Ian Pratt-Hartmann, Lidia Tendera
    Academic press:
    Journal of Logic and Computation (rok: 2017, tom: nie dotyczy, strony: 999-1021), Wydawca: Oxford University Press
    Status:
    Published
    DOI:
    10.1093/logcom/exv075 - link to the publication
  3. 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 (rok: 2018, tom: 19 (2), strony: No. 8), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3174805 - link to the publication
  4. On the Decidability of Elementary Modal Logics
    Authors:
    Jakub Michaliszyn, Jan Otop, Emanuel Kieroński
    Academic press:
    ACM Transactions on Computational Logic (rok: 2015, tom: 17, Issue 1, strony: 2:1--2:47), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/2817825 - link to the publication
  5. 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 (rok: 2016, tom: 17, strony: 32:1--32:38), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/2996796 - link to the publication
  6. Converging to the chase– A tool for finite controllability
    Authors:
    Tomasz Gogacz, Jerzy Marcinkowski
    Academic press:
    Journal of Computer and System Sciences (rok: 2017, tom: 83, strony: 180-206), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2016.08.001 - link to the publication
  7. 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 (rok: 2019, tom: online, strony: brak), Wydawca: Oxford University Press
    Status:
    Published
    DOI:
    10.1093/logcom/exz012 - link to the publication
  8. 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 (rok: 2014, tom: 43, strony: 1012-1063), Wydawca: SIAM
    Status:
    Published
    DOI:
    10.1137/120900095 - link to the publication
  1. Characterizing XML Twig Queries with Examples
    Authors:
    Sławomir Staworko, Piotr Wieczorek
    Conference:
    18th International Conference on Database Theory (ICDT) (rok: 2015, ), Wydawca: Leibniz International Proceedings in Informatics (LIPIcs)
    Data:
    konferencja March 23-27, 2015
    Status:
    Published
    DOI:
    link to the publication
  2. Uniform One-Dimensional Fragments with one Equivalence Relation
    Authors:
    Emanuel Kieroński, Antti Kuusisto
    Conference:
    Computer Science Logic (rok: 2015, ), Wydawca: Leibniz International Proceedings in Informatics (LIPIcs)
    Data:
    konferencja 7-10 September
    Status:
    Published
    DOI:
    link to the publication
  3. Finite Model Reasoning in Expressive Fragments of First-Order Logic
    Authors:
    Lidia Tendera
    Conference:
    the Ninth Workshop on Methods for Modalities (M4M9 2017) (rok: 2017, ), Wydawca: Open Publishing Association, EPTCS
    Data:
    konferencja 8-10 Jan 2017
    Status:
    Published
    DOI:
    link to the publication
  4. Quine's Fluted Fragment is Non-Elementary
    Authors:
    Ian Pratt-Hartmann, Wiesław Szwast, Lidia Tendera
    Conference:
    Computer Science Logic (rok: 2016, ), Wydawca: Leibniz International Proceedings in Informatics (LIPIcs)
    Data:
    konferencja August 29 - September 1
    Status:
    Published
    DOI:
    link to the publication
  5. 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) (rok: 2015, ), Wydawca: IEEE Computer Society Press
    Data:
    konferencja July 6-10 2015
    Status:
    Published
  6. All-instances termination of chase is undecidable
    Authors:
    Tomasz Gogacz, Jerzy Marcinkowski
    Conference:
    Automata, Languages, and Programming: 41st International Colloquium, ICALP (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja July 8-11, 2014
    Status:
    Published
  7. 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 (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja August 26-29, 2014
    Status:
    Published
  8. One-Dimensional Logic over Words
    Authors:
    Emanuel Kieroński
    Conference:
    Computer Science Logic (rok: 2016, ), Wydawca: Leibniz International Proceedings in Informatics (LIPIcs)
    Data:
    konferencja August 29 - September 1
    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 (rok: 2016, ), Wydawca: ACM
    Data:
    konferencja June 26 - July 01
    Status:
    Published
    DOI:
    link to the publication
  10. 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) (rok: 2014, ), Wydawca: ACM
    Data:
    konferencja July 14 - 18, 2014
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy