Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Separability problem in automata theory

2016/21/D/ST6/01376

Keywords:

separability problem characterization problem regular languages tree languages logic

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 Wojciech Czerwiński 

Number of co-investigators in the project: 4

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

Amount awarded: 196 500 PLN

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

Project end date (Y-m-d): 2019-08-07

Project duration:: 30 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. Laptop dla kierownika projektu (8 537 PLN)

Information in the final report

  • Publication in academic press/journals (1)
  • Articles in post-conference publications (6)
  1. Regular Separability of One Counter Automata
    Authors:
    Wojciech Czerwiński, Slawomir Lasota
    Academic press:
    Logical Methods in Computer Science (rok: 2019, tom: 15, strony: 0,0972222222222222), Wydawca: Logical Methods in Computer Science
    Status:
    Published
    DOI:
    10.23638/LMCS-15(2:20)2019 - link to the publication
  1. Regular Separability of Parikh Automata
    Authors:
    Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota, Charles Paperman
    Conference:
    International Colloquium on Automata, Languages, and Programming (ICALP) 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10.07 - 14.07
    Status:
    Published
  2. Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
    Authors:
    Wojciech Czerwinski, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazic, Pawel Parys
    Conference:
    Symposium on Discrete Algorithms (SODA) 2019 (rok: 2019, ), Wydawca: SIAM
    Data:
    konferencja 6-9.01.2019
    Status:
    Published
  3. Regular Separability of Well-Structured Transition Systems
    Authors:
    Wojciech Czerwinski, Slawomir Lasota, Roland Meyer, Sebastian Muskalla, K. Narayan Kumar, Prakash Saivasan
    Conference:
    Conference on Concurrency Theory (CONCUR) 2018 (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 4-7.09.2018
    Status:
    Published
  4. Unboundedness problems for languages of vector addition systems
    Authors:
    Wojciech Czerwiński, Piotr Hofman, Georg Zetzsche
    Conference:
    International Colloquium on Automata, Languages, and Programming (ICALP) 2018 (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-13.07.2018
    Status:
    Published
  5. New Pumping Technique for 2-Dimensional VASS
    Authors:
    Wojciech Czerwiński, Slawomir Lasota, Christof Löding, Radoslaw Piórkowski
    Conference:
    MFCS 2019 (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Data:
    konferencja 26-30.08.2019
    Status:
    Published
  6. The Reachability Problem for Petri Nets is Not Elementary
    Authors:
    Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jérôme Leroux, Filip Mazowiecki
    Conference:
    Symposium on Theory of Computing (STOC) 2019 (rok: 2019, ), Wydawca: ACM
    Data:
    konferencja 23-26.06.2019
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy