Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Niezmienniki numeryczne i strukturalne w algebrze, logice i problemach spełnialności więzów

2014/14/A/ST6/00138

Słowa kluczowe:

rozstrzygalność klasyfikacja modeli spełnialność więzów

Deskryptory:

  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
  • ST1_15: Matematyczne aspekty informatyki
  • ST1_1: Logika i podstawy matematyki

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Uniwersytet Jagielloński, Wydział Matematyki i Informatyki

woj. małopolskie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

prof. Paweł Idziak 

Liczba wykonawców projektu: 7

Konkurs: MAESTRO 6 - ogłoszony 2014-06-16

Przyznana kwota: 2 570 854 PLN

Rozpoczęcie projektu: 2015-10-01

Zakończenie projektu: 2022-09-30

Planowany czas trwania projektu: 84 miesięcy (z wniosku)

Status projektu: Projekt rozliczony

Zakupiona aparatura

  1. Laptopy (2 szt.). Za kwotę 14 528 PLN

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (6)
  • Teksty w publikacjach pokonferencyjnych (17)
  1. A new lower bound for the on-line coloring of intervals with bandwidth
    Autorzy:
    Patryk Mikos
    Czasopismo:
    Theoretical Computer Science (rok: 2018, tom: 708, strony: 96-100), Wydawca: ELSEVIER
    Status:
    Opublikowana
    Doi:
    10.029 - link do publikacji
  2. Satisfiability in multi-valued circuits
    Autorzy:
    Pawel M. Idziak and Jacek Krzaczkowski
    Czasopismo:
    SIAM Journal of Computing (rok: 2022, tom: 51(3), strony: 337-378), Wydawca: SIAM - Society for Industrial and Applied Mathematics
    Status:
    Opublikowana
    Doi:
    10.1137/18M1220194 - link do publikacji
  3. The complexity of counting quantifiers on equality languages
    Autorzy:
    Barnaby Martin, András Pongrácz, Michał Wrona
    Czasopismo:
    Theoretical Computer Science (rok: 2017, tom: 670, strony: 56-67), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2017.01.022 - link do publikacji
  4. The Complexity of Minimal Inference Problem for Conservative Constraint Languages
    Autorzy:
    Michał Wrona
    Czasopismo:
    ACM Transactions on Computational Logic (rok: 2019, tom: 20(2), strony: 12785), Wydawca: ACM - Association for Computing Machinery
    Status:
    Opublikowana
    Doi:
    10.1145/3301410 - link do publikacji
  5. Efficient Enumeration of Non-isomorphic Interval Graphs
    Autorzy:
    Patryk Mikos
    Czasopismo:
    Discrete Mathematics and Theoretical Computer Science (rok: 2021, tom: 23, strony: bd), Wydawca: episciences.org
    Status:
    Opublikowana
    Doi:
    10.46298/dmtcs.6164 - link do publikacji
  6. Equation satisfiability in solvable groups
    Autorzy:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski and Armin Weiß
    Czasopismo:
    Theory of Computing Systems (rok: 2022, tom: 267, strony: N/A), Wydawca: Springer Verlag
    Status:
    Opublikowana
    Doi:
    10.1007/s00224-022-10082-z - link do publikacji
  1. Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
    Autorzy:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski
    Konferencja:
    MFCS - International Symposium on Mathematical Foundations of Computer Science (rok: 2018, ), Wydawca: LIPICS - Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja August 27-31, 2018, Liverpool (UK)
    Status:
    Opublikowana
    Doi:
    link do publikacji
  2. Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width
    Autorzy:
    Michał Wrona
    Konferencja:
    STACS - 37th International Symposium on Theoretical Aspects of Computer Science (rok: 2020, ), Wydawca: Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja March 10 — 13, 2020
    Status:
    Opublikowana
  3. Satisfiability in multi-valued circuits
    Autorzy:
    Paweł Idziak, Jacek Krzaczkowski
    Konferencja:
    LICS - ACM/IEEE Symposium on Logic in Computer Science (rok: 2018, ), Wydawca: Association for Computing Machinery.
    Data:
    konferencja July 9–12, 2018, Oxford, United Kingdom.
    Status:
    Opublikowana
    Doi:
    link do publikacji
  4. Solving Equations–kith and kin
    Autorzy:
    Paweł Idziak, Jacek Krzaczkowski
    Konferencja:
    Algebras and Lattices in Hawai'i (rok: 2018, ), Wydawca: University of Hawaii
    Data:
    konferencja May 22–24, 2018, University of Hawai'i at Manoa
    Status:
    Opublikowana
    Doi:
    link do publikacji
  5. The complexity of minimal inference problem for conservative constraint languages
    Autorzy:
    Michał Wrona
    Konferencja:
    LICS - ACM/IEEE Symposium on Logic in Computer Science (rok: 2017, ), Wydawca: IEEE Computer Society
    Data:
    konferencja June 20-23, 2017
    Status:
    Opublikowana
  6. Satisfiability Problems for Finite Groups
    Autorzy:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski and Armin Weiß
    Konferencja:
    49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) (rok: 2022, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja July 4-8, 2022
    Status:
    Opublikowana
    Doi:
    link do publikacji
  7. Sensitive Instances of the Constraint Satisfaction Problem
    Autorzy:
    Libor Barto, Marcin Kozik, Johnson Tan, Matthew Valeriote
    Konferencja:
    47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja July 8-11, 2020; Saarbrücken, Germany
    Status:
    Opublikowana
  8. Even faster algorithms for CSAT over supernilpotent algebras
    Autorzy:
    Piotr Kawałek, Jacek Krzaczkowski
    Konferencja:
    MFCS - Mathematical Foundations of Computer Science (rok: 2020, ), Wydawca: Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja August 24-28, 2020
    Status:
    Opublikowana
  9. Minimal Inference Problem Over Finite Domains: The Landscape of Complexity
    Autorzy:
    Michał Wrona
    Konferencja:
    Logic Programming and Nonmonotonic Reasoning (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja July 3-6, 2017
    Status:
    Opublikowana
  10. Online Coloring of Short Intervals
    Autorzy:
    Joanna Chybowska-Sokól, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, Adam Polak
    Konferencja:
    Approximation, randomization, and combinatorial optimization : algorithms and techniques (APPROX/RANDOM 2020) (rok: 2020, ), Wydawca: Dagstuhl : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
    Data:
    konferencja August 17-19, 2020
    Status:
    Opublikowana
  11. Satisfiability of Circuits and Equations Over Finite Malcev Algebras
    Autorzy:
    Paweł Idziak, Piotr Kawałek and Jacek Krzaczkowski
    Konferencja:
    39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) (rok: 2022, ), Wydawca: LIPICS - Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja March 15-18, 2022
    Status:
    Opublikowana
  12. The complexity of counting quantifiers on equality languages
    Autorzy:
    Barnaby Martin, András Pongrácz, Michał Wrona
    Konferencja:
    12th Conference on Computability in Europe, Paris, France (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 27.06-1.07.2016
    Status:
    Opublikowana
    Doi:
    link do publikacji
  13. Complexity of Modular Circuits
    Autorzy:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski
    Konferencja:
    37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022) (rok: 2022, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja August 2-5, 2022
    Status:
    Opublikowana
  14. Intermediate problems in modular circuits satisfiability
    Autorzy:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski
    Konferencja:
    35th Annual ACM/IEEE Symposium on Logic in Computer Science (2020) (rok: 2020, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja July 8-11, 2020, Saarbrücken, Germany
    Status:
    Opublikowana
  15. Lower Bounds for On-line Interval Coloring with Vector and Cardinality Constraints
    Autorzy:
    Grzegorz Gutowski, Patryk Mikos
    Konferencja:
    SOFSEM 2017: Theory and Practice of Computer Science, Limerick, Ireland (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 16-20.01.2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  16. Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP
    Autorzy:
    Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk
    Konferencja:
    LICS - 36th Annual ACM/IEEE Symposium on Logic in Computer Science (2021) (rok: 2021, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja 29 June – 02 July 2021
    Status:
    Opublikowana
  17. On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width∗
    Autorzy:
    Michał Wrona
    Konferencja:
    35th Annual ACM/IEEE Symposium on Logic in Computer Science (2020) (rok: 2020, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja July 8-11, 2020, Saarbrücken, Germany
    Status:
    Opublikowana

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy