Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Decidability issues for automata on infinite structures

2014/13/B/ST6/03595

Keywords:

automaton automata on trees

Descriptors:

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

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):

prof. Damian Niwiński 

Number of co-investigators in the project: 10

Call: OPUS 7 - announced on 2014-03-17

Amount awarded: 499 500 PLN

Project start date (Y-m-d): 2015-02-04

Project end date (Y-m-d): 2018-12-03

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

Project status: Project settled

Equipment purchased [PL]

  1. Komputery przenośne (4 231 PLN)
  2. Komputery stacjonarne wraz z monitorami i wyposażeniem (21 000 PLN)
  3. Komputer przenośny (4 231 PLN)
  4. Komputer przenośny (6 000 PLN)

Information in the final report

  • Publication in academic press/journals (4)
  • Articles in post-conference publications (12)
  1. The logical strength of Buchi's decidability theorem
    Authors:
    Leszek Kołodziejczyk, Henryk Michalewski, Pierre Pradic, Michał Skrzypczak
    Academic press:
    Logical Methods in Computer Science (rok: 2019, tom: 15 (2), strony: 16:1-16:31), Wydawca: Logical Methods in Computer Science
    Status:
    Published
    DOI:
    10.23638/LMCS-15(2:16)2019 - link to the publication
  2. Monadic Second Order Logic with Measure and Category Quantifiers
    Authors:
    Matteo Mio, Michał Skrzypczak, Henryk Michalewski
    Academic press:
    Logical Methods in Computer Science (rok: 2018, tom: 14(2), strony: 45320), Wydawca: CoRR
    Status:
    Published
    DOI:
    10.23638/LMCS-14(2:2)2018 - link to the publication
  3. On the Strength of Unambiguous Tree Automata
    Authors:
    Henryk Michalewski, Michal Skrzypczak
    Academic press:
    International Journal of Foundations of Computer Science (rok: 2018, tom: 29(5), strony: 911–933), Wydawca: World Scientific Publishing Company
    Status:
    Published
    DOI:
    10.1142/S012905411842011X - link to the publication
  4. Measure Properties of Regular Sets of Trees
    Authors:
    Tomasz Gogacz, Henryk Michalewski, Matteo Mio, Michał Skrzypczak
    Academic press:
    Information and Computation (rok: 2017, tom: 256, strony: 108-130), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2017.04.012 - link to the publication
  1. On the Complexity of Branching Games with Regular Conditions
    Authors:
    Marcin Przybyłko, Michał Skrzypczak
    Conference:
    41st International Symposium on Mathematical Foundations of Computer Science (MFCS) (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 22.08.2016
    Status:
    Published
    DOI:
    link to the publication
  2. Recognisable Languages over Monads
    Authors:
    Mikołaj Bojańczyk
    Conference:
    Developments in Language Theory - 19th International Conference, DLT 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 27.30.2015
    Status:
    Published
  3. A Characterisation of Pi^0_2 Regular Tree Languages
    Authors:
    Filippo Cavallari, Henryk Michalewski, Michal Skrzypczak
    Conference:
    MFCS 2017 (rok: 2017, ), Wydawca: LIPIcs
    Data:
    konferencja 23 sierpnia 2017
    Status:
    Published
    DOI:
    link to the publication
  4. A Dialectica-Like Interpretation of a Linear MSO on Infinite Words
    Authors:
    Pierre Pradic, Colin Riba
    Conference:
    Foundations of Software Science and Computation Structures (rok: 2019, ), Wydawca: ARCoSS
    Data:
    konferencja 6-11 kwietnia 2019
    Status:
    Published
    DOI:
    link to the publication
  5. Unambiguous Buchi is weak
    Authors:
    Henryk Michalewski, Michał Skrzypczak
    Conference:
    Developments in Language Theory (rok: 2016, ), Wydawca: Springer-Verlag LNCS
    Data:
    konferencja 25.07.2016
    Status:
    Published
  6. How unprovable is Rabin's decidability theorem?
    Authors:
    Leszek Kołodziejczyk, Henryk Michalewski
    Conference:
    Symposium on Logic in Computer Science (LICS) (rok: 2016, ), Wydawca: ACM
    Data:
    konferencja 05.07.2016
    Status:
    Published
    DOI:
    link to the publication
  7. On Determinisation of Good-for-Games Automata
    Authors:
    Denis Kuperberg, Michal Skrzypczak
    Conference:
    Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 06-10.07.2015
    Status:
    Published
    DOI:
    link to the publication
  8. On Unambiguous Regular Tree Languages of Index (0, 2)
    Authors:
    Jacques Duparc, Kevin Fournier, Szczepan Hummel
    Conference:
    24th EACSL Annual Conference on Computer Science Logic, CSL 2015 (rok: 2015, ), Wydawca: Dagstuhl research online publication server
    Data:
    konferencja 7-10.09.2015
    Status:
    Published
    DOI:
    link to the publication
  9. On the Problem of Computing the Probability of Regular Sets of Trees
    Authors:
    Henryk Michalewski, Matteo Mio
    Conference:
    35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015 (rok: 2015, ), Wydawca: Dagstuhl Research Online Publication Server
    Data:
    konferencja 16-18.12.2015
    Status:
    Published
    DOI:
    link to the publication
  10. Measure Quantifier in Monadic Second Order Logic
    Authors:
    Henryk Michalewski, Matteo Mio
    Conference:
    Logical Foundations of Computer Science - International Symposium, LFCS 2016 (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 4-7.01.2016
    Status:
    Published
    DOI:
    link to the publication
  11. Star Height via Games
    Authors:
    Mikołaj Bojańczyk
    Conference:
    30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015 (rok: 2015, ), Wydawca: IEEE Computer Society
    Data:
    konferencja 06.07.2015
    Status:
    Published
  12. The Logical Strength of Büchi's Decidability Theorem
    Authors:
    Leszek Kołodziejczyk, Henryk Michalewski, Pierre Pradic, Michał Skrzypczak
    Conference:
    Computer Science Logic (rok: 2016, ), Wydawca: LIPIcs–Leibniz International Proceedings in Informatics
    Data:
    konferencja 29,09
    Status:
    Published
    DOI:
    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