Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Constraint Satisfaction Problems for infinite homogeneous structures: towards algorithms

2020/37/B/ST6/01179

Keywords:

constraint satisfaction problems algorithmic methods local consistency methods Datalog least fixed-point logic homogeneous structures finitely bounded structures infinite domains computational complexity dichotomy algebraic approach

Descriptors:

  • ST6_004:

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Uniwersytet Jagielloński, Wydział Matematyki i Informatyki

woj. małopolskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Michał Maria Wrona 

Number of co-investigators in the project: 3

Call: OPUS 19 - announced on 2020-03-16

Amount awarded: 331 932 PLN

Project start date (Y-m-d): 2021-01-26

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

Project duration:: 60 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

  • Publication in academic press/journals (1)
  • Articles in post-conference publications (3)
  1. Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough
    Authors:
    Antoine Mottet, Tomas Nagy, Michael Pinsker, Michal Wrona
    Academic press:
    SIAM J. Comput. (rok: 2024, tom: 53(6), strony: 1709-1745), Wydawca: Society for Industrial and Applied Mathematics
    Status:
    Published
    DOI:
    10.1137/22m1538934 - link to the publication
  1. Smooth Approximations and Relational Width Collapses
    Authors:
    Antoine Mottet, Tomás Nagy, Michael Pinsker, Michał Wrona
    Conference:
    48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference) (rok: 2021, tom: ICALP, strony: 138:1-138:20), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 12.07-16.07.2021
    Status:
    Published
    DOI:
    10.4230/LIPIcs.ICALP.2021.138 - link to the publication
  2. Identifying Tractable Quantified Temporal Constraints Within Ord-Horn
    Authors:
    Jakub Rydval, Zaneta Semanisinova, Michał Wrona
    Conference:
    51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (rok: 2024, tom: ICALP 2024, strony: 151:1--151:20), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 08.07.24 - 12.07.24
    Status:
    Published
    DOI:
    10.4230/LIPIcs.ICALP.2024.151 - link to the publication
  3. The complete classification for quantified equality constraints
    Authors:
    Dmitriy Zhuk, Barnaby Martin, Michał Wrona
    Conference:
    Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 (rok: 2023, tom: SODA, strony: 2746-2760), Wydawca: SIAM
    Data:
    konferencja 22.01-25.01.2023
    Status:
    Published
    DOI:
    10.1137/1.9781611977554.ch103 - 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