Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Efficient algorithms for weak forms of non-determinism

2016/21/D/ST6/00491

Keywords:

non-determinism automata 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. Michał Skrzypczak 

Number of co-investigators in the project: 3

Call: SONATA 11 - announced on 2016-03-15

Amount awarded: 273 850 PLN

Project start date (Y-m-d): 2017-02-20

Project end date (Y-m-d): 2020-08-19

Project duration:: 42 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. Tablet.
  2. Komputer stacjonarny (7 000 PLN)
  3. Komputer przenośny (7 000 PLN)

Information in the final report

  • Publication in academic press/journals (2)
  • Articles in post-conference publications (8)
  1. Regular tree languages in low levels of Wadge Hierarchy
    Authors:
    Mikołaj Bojańczyk, Filippo Cavallari, Michał Skrzypczak
    Academic press:
    Logical Methods in Computer Science (rok: 2019, tom: 15(3), strony: 27:1-27:61), Wydawca: Logical Methods in Computer Science
    Status:
    Published
    DOI:
    10.23638/LMCS-15(3:27)2019 - link to the publication
  2. The Uniform Measure of Simple Regular Sets of Infinite Trees
    Authors:
    Marcin Przybyłko, Michał Skrzypczak
    Academic press:
    Information and Computation (rok: 2021, tom: 278, strony: 45315), Wydawca: Elsevier
    Status:
    Accepted for publication
    DOI:
    10.1016/j.ic.2020.104595 - link to the publication
  1. Unambiguous Languages Exhaust the Index Hierarchy
    Authors:
    Michał Skrzypczak
    Conference:
    International Colloquium on Automata, Languages, and Programming (ICALP) (rok: 2018, ), Wydawca: Schloss Dagstuhl, LIPIcs
    Data:
    konferencja 9-13 lipca 2018
    Status:
    Published
  2. On the Succinctness of Alternating Parity Good-for-Games Automata
    Authors:
    Udi Boker, Denis Kuperberg, Karoliina Lehtinen, Michał Skrzypczak
    Conference:
    Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (rok: 2020, ), Wydawca: Schloss Dagstuhl, LIPIcs
    Data:
    konferencja 14-18 grudnia 2020
    Status:
    Accepted for publication
  3. On Computing the Measures of First-Order Definable Sets of Trees
    Authors:
    Marcin Przybyłko
    Conference:
    International Symposium on Games, Automata, Logics, and Formal Verification (GandALF) (rok: 2018, ), Wydawca: Electronic Proceedings in Theoretical Computer Science
    Data:
    konferencja 26-28 września 2018
    Status:
    Published
  4. Uniformisations of Regular Relations Over Bi-Infinite Words
    Authors:
    Grzegorz Fabiański, Michał Skrzypczak, Szymon Toruńczyk
    Conference:
    Logic in Computer Science (LICS) (rok: 2020, ), Wydawca: IEEE Computer Society
    Data:
    konferencja 8-11 lipca 2020
    Status:
    Published
  5. Büchi VASS Recognise ∑11-complete ω-languages
    Authors:
    Michał Skrzypczak
    Conference:
    Reachability Problems (RP) (rok: 2018, ), Wydawca: Springer-Verlag, LNCS
    Data:
    konferencja 24 - 26 września 2018
    Status:
    Published
  6. Uniformisation Gives the Full Strength of Regular Languages
    Authors:
    Nathan Lhote, Vincent Michielini, Michał Skrzypczak
    Conference:
    Mathematical Foundations of Computer Science (MFCS) (rok: 2019, ), Wydawca: Schloss Dagstuhl, LIPIcs
    Data:
    konferencja 26-30 sierpnia 2019
    Status:
    Published
  7. How Deterministic are Good-For-Games Automata?
    Authors:
    Udi Boker, Orna Kupferman, Michał Skrzypczak
    Conference:
    Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (rok: 2017, ), Wydawca: Schloss Dagstuhl, LIPIcs
    Data:
    konferencja 11-15 grudnia 2017
    Status:
    Published
  8. Regular Choice Functions and Uniformisations For countable Domains
    Authors:
    Vincent Michielini, Michał Skrzypczak
    Conference:
    Mathematical Foundations of Computer Science (MFCS) (rok: 2020, ), Wydawca: Schloss Dagstuhl, LIPIcs
    Data:
    konferencja 24-28 sierpnia 2020
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy