Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Computational aspects of infinite-duration games

2021/41/B/ST6/03914

Keywords:

infinite-duration games parity games quasi-polynomial algorithm meand-payoff games discounted-payoff games stochastic games mu-calculus lower bounds infinite trees Mostowski index problem

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • 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.

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Paweł Czesław Parys 

Number of co-investigators in the project: 8

Call: OPUS 21 - announced on 2021-03-15

Amount awarded: 937 570 PLN

Project start date (Y-m-d): 2022-01-21

Project end date (Y-m-d): 2026-01-20

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

Project status: Pending project

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.

Information in the final report

  • Articles in post-conference publications (7)
  1. The Probabilistic Rabin Tree Theorem
    Authors:
    Damian Niwiński, Paweł Parys, Michał Skrzypczak
    Conference:
    Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science (rok: 2023, tom: 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2023), strony: nieznane), Wydawca: ACM/IEEE
    Data:
    konferencja 26-29.06.2023
    Status:
    Submitted
  2. Languages Given by Finite Automata over the Unary Alphabet
    Authors:
    Wojciech Czerwiński, Maciej Dębski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michał Skrzypczak, Frank Stephan, Christopher Tan
    Conference:
    43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023, December 18-20, 2023, IIIT Hyderabad, Telangana, India (rok: 2023, tom: 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023), strony: 22:1-22:20), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Data:
    konferencja 18-20.122023
    Status:
    Published
    DOI:
    10.4230/LIPIcs.FSTTCS.2023.22 - link to the publication
  3. Parity Games of Bounded Tree-Depth
    Authors:
    Konrad Staniszewski
    Conference:
    31st EACSL Annual Conference on Computer Science Logic, CSL 2023, February 13-16, 2023, Warsaw, Poland (rok: 2023, tom: 31st EACSL Annual Conference on Computer Science Logic (CSL 2023), strony: 33:1-33:20), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Data:
    konferencja 13-16.02.2023
    Status:
    Published
    DOI:
    10.4230/LIPIcs.CSL.2023.33 - link to the publication
  4. The Probabilistic Rabin Tree Theorem
    Authors:
    Damian Niwiński, Paweł Parys, Michał Skrzypczak
    Conference:
    Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science (rok: 2023, tom: 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2023), strony: 45670), Wydawca: ACM/IEEE
    Data:
    konferencja 26-29.06.2023
    Status:
    Published
    DOI:
    10.1109/LICS56636.2023.10175800 - link to the publication
  5. Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games
    Authors:
    Paweł Parys, Aleksander Wiącek
    Conference:
    Unity of Logic and Computation - 19th Conference on Computability in Europe, CiE 2023 (rok: 2023, tom: Unity of Logic and Computation - 19th Conference on Computability in Europe, CiE 2023, strony: nieznane), Wydawca: Springer
    Data:
    konferencja 24-28.07.2023
    Status:
    Submitted
  6. Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games
    Authors:
    Paweł Parys, Aleksander Wiącek
    Conference:
    Unity of Logic and Computation - 19th Conference on Computability in Europe, CiE 2023 (rok: 2023, tom: Unity of Logic and Computation - 19th Conference on Computability in Europe, CiE 2023, strony: 275-286), Wydawca: Springer
    Data:
    konferencja 24-28.07.2023
    Status:
    Published
    DOI:
    10.1007/978-3-031-36978-0_22 - link to the publication
  7. Parity Games of Bounded Tree-Depth
    Authors:
    Konrad Staniszewski
    Conference:
    31st EACSL Annual Conference on Computer Science Logic, CSL 2023, February 13-16, 2023, Warsaw, Poland (rok: 2023, tom: 31st EACSL Annual Conference on Computer Science Logic (CSL 2023), strony: 33:1-33:20), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Data:
    konferencja 13-16.02.2023
    Status:
    Published
    DOI:
    10.4230/LIPIcs.CSL.2023.33 - link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy