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

Other projects carried out by the institution »

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]

  1. Komputer przenośny. Cost: 7 000 PLN
  2. Komputer stacjonarny. Cost: 7 000 PLN
  3. Tablet.

Information in the final report

Publication in academic press/journals (2)

  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 (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
  2. 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)

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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

« New search

Graphic design and implementation: Jakub Piotrowski