Zmiana języka

Projects search

Quantitative properties for higher-order recursion schemes

2016/22/E/ST6/00041

Keywords

Descriptors

  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna

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

Voivodeship: 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
2017-04-12
Project end date
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 pcs). Cost: 12 000 PLN
  2. Urządzenie wielofunkcyjne (2 sztuki).

Information in the final report

Publication in academic press/journals (6)

  1. Cost Automata, Safe Schemes, and Downward Closures

    Authors:
    David Barozzini, Lorenzo Clemente, Thomas Colcombet, Paweł Parys
    Academic press:
    Fundamenta Informaticae (year: 2022, volume: 188(3), pages: 127-178), Publisher: Polskie Towarzystwo Matematyczne, IOS Press
    Status:
    Published
    DOI:
    10.3233/FI-222145 – link to the publication

  2. Recursion Schemes, the MSO Logic, and the U quantifier

    Authors:
    Paweł Parys
    Academic press:
    Logical Methods in Computer Science (year: 2020, volume: 16(1), pages: 20:1-20:23), Publisher: Logical Methods in Computer Science
    Status:
    Published
    DOI:
    10.23638/LMCS-16(1:20)2020 – link to the publication

  3. A Type System Describing Unboundedness

    Authors:
    Paweł Parys
    Academic press:
    Discrete Mathematics & Theoretical Computer Science (year: 2020, volume: 22(4), pages: 2:1-2:84), Publisher: Inria
    Status:
    Published
    DOI:
    10.23638/DMTCS-22-4-2 – link to the publication

  4. The Caucal Hierarchy: Interpretations in the (W)MSO+U Logic

    Authors:
    Paweł Parys
    Academic press:
    Information and Computation (year: 2022, volume: 286, pages: 104782:1-23), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2021.104782 – link to the publication

  5. 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 (year: 2022, volume: 18, pages: 8:1-8:18), Publisher: Logical Methods in Computer Science
    Status:
    Published
    DOI:
    10.46298/lmcs-18(1:8)2022 – link to the publication

  6. On the expressive power of non-deterministic and unambiguous Petri nets over infinite words

    Authors:
    Olivier Finkel, Michał Skrzypczak
    Academic press:
    Fundamenta Informaticae (year: 2021, volume: 183, pages: 243-291), Publisher: Polskie Towarzystwo Matematyczne, IOS Press
    Status:
    Published
    DOI:
    10.3233/FI-2021-2088 – link to the publication

Articles in post-conference publications (18)

  1. Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time

    Authors:
    Paweł Parys
    Conference:
    44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (year: 2019, pages: 10:1-10:13), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 26-30.08.2019
    Status:
    Published

  2. 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) (year: 2017, pages: 56:1-56:14), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 21-25.08.2017
    Status:
    Published

  3. Recursion Schemes and the WMSO+U Logic

    Authors:
    Paweł Parys
    Conference:
    35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) (year: 2018, pages: 53:1-53:16), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 28.02-3.03.2018
    Status:
    Published

  4. Extensions of the Caucal Hierarchy?

    Authors:
    Paweł Parys
    Conference:
    13th International Conference on Language and Automata Theory and Applications (LATA 2019) (year: 2019, pages: 368-380), Publisher: Springer
    Date:
    conference 26-29.03.2019
    Status:
    Published

  5. Homogeneity without Loss of Generality

    Authors:
    Paweł Parys
    Conference:
    Third International Conference on Formal Structures for Computation and Deduction (FSCD 2018) (year: 2018, pages: 27:1-27:15), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 9-12.07.2018
    Status:
    Published

  6. Intersection Types for Unboundedness Problems

    Authors:
    Paweł Parys
    Conference:
    Ninth Workshop on Intersection Types and Related Systems (ITRS 2018) (year: 2018, pages: 46230), Publisher: Open Publishing Association
    Date:
    conference 8.07.2018
    Status:
    Published

  7. 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 (year: 2020, pages: 136:1-136:18), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 8-11.07.2020
    Status:
    Published

  8. 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 (year: 2020, pages: 53:1-53:14), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 14-18.12.2020
    Status:
    Published

  9. 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 (year: 2020, pages: 109:1-109:18), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 8-11.07.2020
    Status:
    Published

  10. Parity Games: Another View on the Lehtinen's Algorithm

    Authors:
    Paweł Parys
    Conference:
    28th EACSL Annual Conference on Computer Science Logic, CSL 2020 (year: 2020, pages: 32:1-32:15), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 13-16.01.2020
    Status:
    Published

  11. 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 (year: 2020, pages: 521-534), Publisher: IEEE
    Date:
    conference 8-11.07.2020
    Status:
    Published

  12. 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 (year: 2021, pages: 9:1-9:23), Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Date:
    conference 25-28.01.2021
    Status:
    Published

  13. 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 (year: 2022, pages: 112:1-112:19), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 4-8.07.2022
    Status:
    Published

  14. 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) (year: 2019, pages: 46035), Publisher: IEEE
    Date:
    conference 24-27.06.2019
    Status:
    Published

  15. On Guidable Index of Tree Automata

    Authors:
    Damian Niwiński, Michał Skrzypczak
    Conference:
    46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 (year: 2021, pages: 81:1-81:14), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 23-27.08.2021
    Status:
    Published

  16. 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 (year: 2021, pages: 395-405), Publisher: Springer
    Date:
    conference 28.06-2.07.2021
    Status:
    Published

  17. Higher-Order Model Checking Step by Step

    Authors:
    Paweł Parys
    Conference:
    The 48th International Colloquium on Automata, Languages and Programming, ICALP 2021 (year: 2021, pages: 140:1-140:16), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 12-16.07.2021
    Status:
    Published

  18. 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) (year: 2017, pages: 45:1-45:14), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 11-15.12.2017
    Status:
    Published

« New search

Graphic design and implementation: Jakub Piotrowski