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
Principal investigator (from the host institution)
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]
- Notebook lub laptop (4 pcs). Cost: 30 000 PLN
Information in the final report
Publication in academic press/journals (8)
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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)
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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