Efficient algorithms for weak forms of non-determinism
2016/21/D/ST6/00491
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
Principal investigator (from the host institution)
dr hab. Michał Paweł 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
- 2017-02-20
- Project end date
- 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]
- Komputer przenośny. Cost: 7 000 PLN
- Komputer stacjonarny. Cost: 7 000 PLN
- Tablet.
Information in the final report
Publication in academic press/journals (2)
-
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 (year: 2019, volume: 15(3), pages: 27:1-27:61), Publisher: Logical Methods in Computer Science
- Status:
- Published
- DOI:
- 10.23638/LMCS-15(3:27)2019 – link to the publication
-
The Uniform Measure of Simple Regular Sets of Infinite Trees
- Authors:
- Marcin Przybyłko, Michał Skrzypczak
- Status:
- Accepted for publication
Articles in post-conference publications (8)
-
Büchi VASS Recognise ∑11-complete ω-languages
- Authors:
- Michał Skrzypczak
- Conference:
- Reachability Problems (RP) (year: 2018, pages: 133-145), Publisher: Springer-Verlag, LNCS
- Date:
- conference 24 - 26 września 2018
- Status:
- Published
-
How Deterministic are Good-For-Games Automata?
- Authors:
- Udi Boker, Orna Kupferman, Michał Skrzypczak
- Conference:
- Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (year: 2017, pages: 18:1-18:14), Publisher: Schloss Dagstuhl, LIPIcs
- Date:
- conference 11-15 grudnia 2017
- Status:
- Published
-
Unambiguous Languages Exhaust the Index Hierarchy
- Authors:
- Michał Skrzypczak
- Conference:
- International Colloquium on Automata, Languages, and Programming (ICALP) (year: 2018, pages: 140:1-140:14), Publisher: Schloss Dagstuhl, LIPIcs
- Date:
- conference 9-13 lipca 2018
- Status:
- Published
-
Uniformisations of Regular Relations Over Bi-Infinite Words
- Authors:
- Grzegorz Fabiański, Michał Skrzypczak, Szymon Toruńczyk
- Conference:
- Logic in Computer Science (LICS) (year: 2020, pages: 384-396), Publisher: IEEE Computer Society
- Date:
- conference 8-11 lipca 2020
- Status:
- Published
-
Regular Choice Functions and Uniformisations For countable Domains
- Authors:
- Vincent Michielini, Michał Skrzypczak
- Conference:
- Mathematical Foundations of Computer Science (MFCS) (year: 2020, pages: 69:1-69:13), Publisher: Schloss Dagstuhl, LIPIcs
- Date:
- conference 24-28 sierpnia 2020
- Status:
- Published
-
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) (year: 2018, pages: 206-219), Publisher: Electronic Proceedings in Theoretical Computer Science
- Date:
- conference 26-28 września 2018
- Status:
- Published
-
Uniformisation Gives the Full Strength of Regular Languages
- Authors:
- Nathan Lhote, Vincent Michielini, Michał Skrzypczak
- Conference:
- Mathematical Foundations of Computer Science (MFCS) (year: 2019, pages: 61:1-61:13), Publisher: Schloss Dagstuhl, LIPIcs
- Date:
- conference 26-30 sierpnia 2019
- Status:
- Published
-
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) (year: 2020, pages: 48:1–48:13), Publisher: Schloss Dagstuhl, LIPIcs
- Status:
- Accepted for publication