Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Structure and algorithms for graph classes defined by transduction-closed properties

2022/47/D/ST6/03421

Keywords:

FO logic bounded expansion monadic stability nowhere dense interpretations transductions model checking twin-width monadically NIP graph classes

Descriptors:

  • ST6_004:
  • ST6_006:

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 Jakub Gajarský 

Number of co-investigators in the project: 2

Call: SONATA 18 - announced on 2022-07-15

Amount awarded: 508 440 PLN

Project start date (Y-m-d): 2023-10-02

Project end date (Y-m-d): 2026-10-01

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

Project status: Pending project

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.

Information in the final report

  • Articles in post-conference publications (2)
  1. Elementary first-order model checking for sparse graphs
    Authors:
    Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski, Giannos Stamoulis, Szymon Toruńczyk
    Conference:
    Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, July 8-11, 2024 (rok: 2024, tom: 39th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), strony: 36:1-36:14), Wydawca: ACM
    Data:
    konferencja July 8-11, 2024
    Status:
    Published
    DOI:
    10.1145/3661814.3662094 - link to the publication
  2. On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification
    Authors:
    Jakub Gajarský, Rose McCarty
    Conference:
    51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (rok: 2024, tom: 51st International Colloquium on Automata, Languages, and Programming (ICALP), strony: 137:1-137:20), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Data:
    konferencja July 8-12, 2024
    Status:
    Published
    DOI:
    10.4230/LIPIcs.ICALP.2024.137 - 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