Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Własności ilościowe dla schematów rekurencyjnych wyższego rzędu

2016/22/E/ST6/00041

Słowa kluczowe:

teoria automatów własności ilościowe schematy rekurencyjne wyższego rzędu typy przecięciowe kwantyfikator nieograniczoności rozstrzygalność

Deskryptory:

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

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr hab. Paweł Parys 

Liczba wykonawców projektu: 6

Konkurs: SONATA BIS 6 - ogłoszony 2016-06-15

Przyznana kwota: 1 102 049 PLN

Rozpoczęcie projektu: 2017-04-12

Zakończenie projektu: 2023-04-11

Planowany czas trwania projektu: 72 miesięcy (z wniosku)

Status projektu: Projekt rozliczony

Opis Projektu

Pobierz opis projektu w formacie .pdf

Uwaga - opisy projektów zostały sporządzone przez samych autorów wniosków i w niezmienionej formie umieszczone w systemie.

Zakupiona aparatura

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

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (6)
  • Teksty w publikacjach pokonferencyjnych (19)
  1. On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
    Autorzy:
    Olivier Finkel, Michał Skrzypczak
    Czasopismo:
    Fundamenta Informaticae (rok: 2021, tom: 183, strony: 243-291), Wydawca: Polskie Towarzystwo Matematyczne, IOS Press
    Status:
    Opublikowana
    Doi:
    10.3233/FI-2021-2088 - link do publikacji
  2. A Recursive Approach to Solving Parity Games in Quasipolynomial Time
    Autorzy:
    Karoliina Lehtinen, Paweł Parys, Sven Schewe, Dominik Wojtczak
    Czasopismo:
    Logical Methods in Computer Science (rok: 2022, tom: 18, strony: 8:1-8:18), Wydawca: Logical Methods in Computer Science
    Status:
    Opublikowana
    Doi:
    10.46298/lmcs-18(1:8)2022 - link do publikacji
  3. Recursion Schemes, the MSO Logic, and the U quantifier
    Autorzy:
    Paweł Parys
    Czasopismo:
    Logical Methods in Computer Science (rok: 2020, tom: 16(1), strony: 20:1-20:23), Wydawca: Logical Methods in Computer Science
    Status:
    Opublikowana
    Doi:
    10.23638/LMCS-16(1:20)2020 - link do publikacji
  4. The Caucal Hierarchy: Interpretations in the (W)MSO+U Logic
    Autorzy:
    Paweł Parys
    Czasopismo:
    Information and Computation (rok: 2022, tom: 286, strony: 104782:1-23), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.ic.2021.104782 - link do publikacji
  5. A Type System Describing Unboundedness
    Autorzy:
    Paweł Parys
    Czasopismo:
    Discrete Mathematics & Theoretical Computer Science (rok: 2020, tom: 22(4), strony: 2:1-2:84), Wydawca: Inria
    Status:
    Opublikowana
    Doi:
    10.23638/DMTCS-22-4-2 - link do publikacji
  6. Cost Automata, Safe Schemes, and Downward Closures
    Autorzy:
    David Barozzini, Lorenzo Clemente, Thomas Colcombet, Paweł Parys
    Czasopismo:
    Fundamenta Informaticae (rok: 2022, tom: 188(3), strony: 127-178), Wydawca: Polskie Towarzystwo Matematyczne, IOS Press
    Status:
    Opublikowana
    Doi:
    10.3233/FI-222145 - link do publikacji
  1. Bisimulation Finiteness of Pushdown Systems Is Elementary
    Autorzy:
    Stefan Göller, Paweł Parys
    Konferencja:
    Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 (rok: 2020, ), Wydawca: IEEE
    Data:
    konferencja 8-11.07.2020
    Status:
    Opublikowana
  2. Cost Automata, Safe Schemes, and Downward Closures
    Autorzy:
    David Barozzini, Lorenzo Clemente, Thomas Colcombet, Paweł Parys
    Konferencja:
    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:
    Opublikowana
  3. Extensions of the Caucal Hierarchy?
    Autorzy:
    Paweł Parys
    Konferencja:
    13th International Conference on Language and Automata Theory and Applications (LATA 2019) (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 26-29.03.2019
    Status:
    Opublikowana
  4. Higher-Order Model Checking Step by Step
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowana
  5. Shelah-Stupp's and Muchnik's Iterations Revisited
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowana
  6. Intersection Types for Unboundedness Problems
    Autorzy:
    Paweł Parys
    Konferencja:
    Ninth Workshop on Intersection Types and Related Systems (ITRS 2018) (rok: 2018, ), Wydawca: Open Publishing Association
    Data:
    konferencja 8.07.2018
    Status:
    Opublikowana
  7. Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowana
  8. Unboundedness for Recursion Schemes: A Simpler Type System
    Autorzy:
    David Barozzini, Paweł Parys and Jan Wróblewski
    Konferencja:
    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:
    Opublikowana
  9. Higher-Order Nonemptiness Step by Step
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowana
  10. Homogeneity without Loss of Generality
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowana
  11. MSO+Nabla Is Undecidable
    Autorzy:
    Mikołaj Bojańczyk, Edon Kelmendi, Michał Skrzypczak
    Konferencja:
    Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019) (rok: 2019, ), Wydawca: IEEE
    Data:
    konferencja 24-27.06.2019
    Status:
    Opublikowana
  12. The Complexity of the Diagonal Problem for Recursion Schemes
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowana
  13. A Characterisation of Pi^0_2 Regular Tree Languages
    Autorzy:
    Filippo Cavallari, Henryk Michalewski, Michał Skrzypczak
    Konferencja:
    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:
    Opublikowana
  14. A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation
    Autorzy:
    André Arnold, Damian Niwiński, Paweł Parys
    Konferencja:
    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:
    Opublikowana
  15. Computing Measures of Weak-MSO Definable Sets of Trees
    Autorzy:
    Damian Niwiński, Marcin Przybyłko, Michał Skrzypczak
    Konferencja:
    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:
    Opublikowana
  16. On Guidable Index of Tree Automata
    Autorzy:
    Damian Niwiński, Michał Skrzypczak
    Konferencja:
    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:
    Opublikowana
  17. Parity Games: Another View on the Lehtinen's Algorithm
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowana
  18. Recursion Schemes and the WMSO+U Logic
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowana
  19. Extending the WMSO+U Logic With Quantification Over Tuples
    Autorzy:
    Anita Badyl, Paweł Parys
    Konferencja:
    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:
    Złożona

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy