Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Quantitative properties for higher-order recursion schemes

2016/22/E/ST6/00041

Keywords:

automata theory quantitative properties higher-order recursion schemes intersection types unbounding quantifier decidability

Descriptors:

  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms

Panel:

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

Host institution :

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Paweł Parys 

Number of co-investigators in the project: 6

Call: SONATA BIS 6 - announced on 2016-06-15

Amount awarded: 1 102 049 PLN

Project start date (Y-m-d): 2017-04-12

Project end date (Y-m-d): 2023-04-11

Project duration:: 72 months (the same as in the proposal)

Project status: Project settled

Project description

Download the project description in a pdf file

Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Equipment purchased [PL]

  1. Komputer typu laptop (2 szt.) (12 000 PLN)
  2. Urządzenie wielofunkcyjne (2 sztuki).

Information in the final report

  • Publication in academic press/journals (6)
  • Articles in post-conference publications (19)
  1. Recursion Schemes, the MSO Logic, and the U quantifier
    Authors:
    Paweł Parys
    Academic press:
    Logical Methods in Computer Science (rok: 2020, tom: 16(1), strony: 20:1-20:23), Wydawca: Logical Methods in Computer Science
    Status:
    Published
    DOI:
    10.23638/LMCS-16(1:20)2020 - link to the publication
  2. A Type System Describing Unboundedness
    Authors:
    Paweł Parys
    Academic press:
    Discrete Mathematics & Theoretical Computer Science (rok: 2020, tom: 22(4), strony: 2:1-2:84), Wydawca: Inria
    Status:
    Published
    DOI:
    10.23638/DMTCS-22-4-2 - link to the publication
  3. Cost Automata, Safe Schemes, and Downward Closures
    Authors:
    David Barozzini, Lorenzo Clemente, Thomas Colcombet, Paweł Parys
    Academic press:
    Fundamenta Informaticae (rok: 2022, tom: 188(3), strony: 127-178), Wydawca: Polskie Towarzystwo Matematyczne, IOS Press
    Status:
    Published
    DOI:
    10.3233/FI-222145 - link to the publication
  4. A Recursive Approach to Solving Parity Games in Quasipolynomial Time
    Authors:
    Karoliina Lehtinen, Paweł Parys, Sven Schewe, Dominik Wojtczak
    Academic press:
    Logical Methods in Computer Science (rok: 2022, tom: 18, strony: 8:1-8:18), Wydawca: Logical Methods in Computer Science
    Status:
    Published
    DOI:
    10.46298/lmcs-18(1:8)2022 - link to the publication
  5. On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
    Authors:
    Olivier Finkel, Michał Skrzypczak
    Academic press:
    Fundamenta Informaticae (rok: 2021, tom: 183, strony: 243-291), Wydawca: Polskie Towarzystwo Matematyczne, IOS Press
    Status:
    Published
    DOI:
    10.3233/FI-2021-2088 - link to the publication
  6. The Caucal Hierarchy: Interpretations in the (W)MSO+U Logic
    Authors:
    Paweł Parys
    Academic press:
    Information and Computation (rok: 2022, tom: 286, strony: 104782:1-23), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2021.104782 - link to the publication
  1. Cost Automata, Safe Schemes, and Downward Closures
    Authors:
    David Barozzini, Lorenzo Clemente, Thomas Colcombet, Paweł Parys
    Conference:
    The 47th International Colloquium on Automata, Languages and Programming, ICALP 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 8-11.07.2020
    Status:
    Published
  2. Intersection Types for Unboundedness Problems
    Authors:
    Paweł Parys
    Conference:
    Ninth Workshop on Intersection Types and Related Systems (ITRS 2018) (rok: 2018, ), Wydawca: Open Publishing Association
    Data:
    konferencja 8.07.2018
    Status:
    Published
  3. Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
    Authors:
    Paweł Parys
    Conference:
    44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 26-30.08.2019
    Status:
    Published
  4. Shelah-Stupp's and Muchnik's Iterations Revisited
    Authors:
    Paweł Parys
    Conference:
    Computer Science - Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021 (rok: 2021, ), Wydawca: Springer
    Data:
    konferencja 28.06-2.07.2021
    Status:
    Published
  5. A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation
    Authors:
    André Arnold, Damian Niwiński, Paweł Parys
    Conference:
    29th EACSL Annual Conference on Computer Science Logic, CSL 2021 (rok: 2021, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Data:
    konferencja 25-28.01.2021
    Status:
    Published
  6. Bisimulation Finiteness of Pushdown Systems Is Elementary
    Authors:
    Stefan Göller, Paweł Parys
    Conference:
    Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 (rok: 2020, ), Wydawca: IEEE
    Data:
    konferencja 8-11.07.2020
    Status:
    Published
  7. Extensions of the Caucal Hierarchy?
    Authors:
    Paweł Parys
    Conference:
    13th International Conference on Language and Automata Theory and Applications (LATA 2019) (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 26-29.03.2019
    Status:
    Published
  8. MSO+Nabla Is Undecidable
    Authors:
    Mikołaj Bojańczyk, Edon Kelmendi, Michał Skrzypczak
    Conference:
    Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019) (rok: 2019, ), Wydawca: IEEE
    Data:
    konferencja 24-27.06.2019
    Status:
    Published
  9. Parity Games: Another View on the Lehtinen's Algorithm
    Authors:
    Paweł Parys
    Conference:
    28th EACSL Annual Conference on Computer Science Logic, CSL 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 13-16.01.2020
    Status:
    Published
  10. Unboundedness for Recursion Schemes: A Simpler Type System
    Authors:
    David Barozzini, Paweł Parys and Jan Wróblewski
    Conference:
    The 49th International Colloquium on Automata, Languages and Programming, ICALP 2022 (rok: 2022, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 4-8.07.2022
    Status:
    Published
  11. The Complexity of the Diagonal Problem for Recursion Schemes
    Authors:
    Paweł Parys
    Conference:
    37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 11-15.12.2017
    Status:
    Published
  12. A Characterisation of Pi^0_2 Regular Tree Languages
    Authors:
    Filippo Cavallari, Henryk Michalewski, Michał Skrzypczak
    Conference:
    42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 21-25.08.2017
    Status:
    Published
  13. Homogeneity without Loss of Generality
    Authors:
    Paweł Parys
    Conference:
    Third International Conference on Formal Structures for Computation and Deduction (FSCD 2018) (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-12.07.2018
    Status:
    Published
  14. On Guidable Index of Tree Automata
    Authors:
    Damian Niwiński, Michał Skrzypczak
    Conference:
    46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 (rok: 2021, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 23-27.08.2021
    Status:
    Published
  15. Computing Measures of Weak-MSO Definable Sets of Trees
    Authors:
    Damian Niwiński, Marcin Przybyłko, Michał Skrzypczak
    Conference:
    The 47th International Colloquium on Automata, Languages and Programming, ICALP 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 8-11.07.2020
    Status:
    Published
  16. Higher-Order Model Checking Step by Step
    Authors:
    Paweł Parys
    Conference:
    The 48th International Colloquium on Automata, Languages and Programming, ICALP 2021 (rok: 2021, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 12-16.07.2021
    Status:
    Published
  17. Higher-Order Nonemptiness Step by Step
    Authors:
    Paweł Parys
    Conference:
    40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 14-18.12.2020
    Status:
    Published
  18. Recursion Schemes and the WMSO+U Logic
    Authors:
    Paweł Parys
    Conference:
    35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 28.02-3.03.2018
    Status:
    Published
  19. Extending the WMSO+U Logic With Quantification Over Tuples
    Authors:
    Anita Badyl, Paweł Parys
    Conference:
    50th EATCS International Colloquium on Automata, Languages and Programming, ICALP 2023 (rok: 2023, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10-14.07.2023
    Status:
    Submitted

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy