Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Manuel Bodirsky and Simon Knäuer. Network Satisfaction Problems Solved by k-Consistency. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 116:1-116:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2023.116, author = {Bodirsky, Manuel and Kn\"{a}uer, Simon}, title = {{Network Satisfaction Problems Solved by k-Consistency}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {116:1--116:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.116}, URN = {urn:nbn:de:0030-drops-181680}, doi = {10.4230/LIPIcs.ICALP.2023.116}, annote = {Keywords: Constraint Satisfaction, Computational Complexity, Relation Algebras, Network Satisfaction, Qualitative Reasoning, k-Consistency, Datalog} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Manuel Bodirsky, Simon Knäuer, and Sebastian Rudolph. Datalog-Expressibility for Monadic and Guarded Second-Order Logic. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 120:1-120:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2021.120, author = {Bodirsky, Manuel and Kn\"{a}uer, Simon and Rudolph, Sebastian}, title = {{Datalog-Expressibility for Monadic and Guarded Second-Order Logic}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {120:1--120:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.120}, URN = {urn:nbn:de:0030-drops-141897}, doi = {10.4230/LIPIcs.ICALP.2021.120}, annote = {Keywords: Monadic Second-order Logic, Guarded Second-order Logic, Datalog, constraint satisfaction, homomorphism-closed, conjunctive query, primitive positive formula, pebble game, \omega-categoricity} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Michał Wrona. Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{wrona:LIPIcs.STACS.2020.39, author = {Wrona, Micha{\l}}, title = {{Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {39:1--39:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.39}, URN = {urn:nbn:de:0030-drops-119000}, doi = {10.4230/LIPIcs.STACS.2020.39}, annote = {Keywords: Constraint Satisfaction, Homogeneous Graphs, Bounded Width, Strict Width, Relational Width, Computational Complexity} }
Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Manuel Bodirsky, Marcello Mamino, and Caterina Viola. Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bodirsky_et_al:LIPIcs.CSL.2018.12, author = {Bodirsky, Manuel and Mamino, Marcello and Viola, Caterina}, title = {{Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains}}, booktitle = {27th EACSL Annual Conference on Computer Science Logic (CSL 2018)}, pages = {12:1--12:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-088-0}, ISSN = {1868-8969}, year = {2018}, volume = {119}, editor = {Ghica, Dan R. and Jung, Achim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.12}, URN = {urn:nbn:de:0030-drops-96792}, doi = {10.4230/LIPIcs.CSL.2018.12}, annote = {Keywords: Valued constraint satisfaction problems, Piecewise linear functions, Submodular functions, Semilinear, Constraint satisfaction, Optimisation, Model Theory} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Manuel Bodirsky, Barnaby Martin, Marcello Mamino, and Antoine Mottet. The Complexity of Disjunctive Linear Diophantine Constraints. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bodirsky_et_al:LIPIcs.MFCS.2018.33, author = {Bodirsky, Manuel and Martin, Barnaby and Mamino, Marcello and Mottet, Antoine}, title = {{The Complexity of Disjunctive Linear Diophantine Constraints}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {33:1--33:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.33}, URN = {urn:nbn:de:0030-drops-96150}, doi = {10.4230/LIPIcs.MFCS.2018.33}, annote = {Keywords: Constraint Satisfaction, Presburger Arithmetic, Computational Complexity} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Manuel Bodirsky and Marcello Mamino. Constraint Satisfaction Problems over Numeric Domains. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 79-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{bodirsky_et_al:DFU.Vol7.15301.79, author = {Bodirsky, Manuel and Mamino, Marcello}, title = {{Constraint Satisfaction Problems over Numeric Domains}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {79--111}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.79}, URN = {urn:nbn:de:0030-drops-69580}, doi = {10.4230/DFU.Vol7.15301.79}, annote = {Keywords: Constraint satisfaction problems, Numerical domains} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz. Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 119:1-119:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2016.119, author = {Bodirsky, Manuel and Martin, Barnaby and Pinsker, Michael and Pongr\'{a}cz, Andr\'{a}s}, title = {{Constraint Satisfaction Problems for Reducts of Homogeneous Graphs}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {119:1--119:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.119}, URN = {urn:nbn:de:0030-drops-62543}, doi = {10.4230/LIPIcs.ICALP.2016.119}, annote = {Keywords: Constraint Satisfaction, Homogeneous Graphs, Computational Complexity, Universal Algebra, Ramsey Theory} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. The Complexity of Phylogeny Constraint Satisfaction. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bodirsky_et_al:LIPIcs.STACS.2016.20, author = {Bodirsky, Manuel and Jonsson, Peter and Van Pham, Trung}, title = {{The Complexity of Phylogeny Constraint Satisfaction}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {20:1--20:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.20}, URN = {urn:nbn:de:0030-drops-57218}, doi = {10.4230/LIPIcs.STACS.2016.20}, annote = {Keywords: constraint satisfaction problems, computational complexity, phylogenetic reconstruction, ramsey theory, model theory} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Manuel Bodirsky. The Complexity of Constraint Satisfaction Problems (Invited Talk). In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 2-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bodirsky:LIPIcs.STACS.2015.2, author = {Bodirsky, Manuel}, title = {{The Complexity of Constraint Satisfaction Problems}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {2--9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.2}, URN = {urn:nbn:de:0030-drops-49567}, doi = {10.4230/LIPIcs.STACS.2015.2}, annote = {Keywords: constraint satisfaction, universal algebra, model theory, clones, temporal and spatial reasoning} }
Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)
Manuel Bodirsky and Michal Wrona. Equivalence Constraint Satisfaction Problems. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 122-136, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{bodirsky_et_al:LIPIcs.CSL.2012.122, author = {Bodirsky, Manuel and Wrona, Michal}, title = {{Equivalence Constraint Satisfaction Problems}}, booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL}, pages = {122--136}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-42-2}, ISSN = {1868-8969}, year = {2012}, volume = {16}, editor = {C\'{e}gielski, Patrick and Durand, Arnaud}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.122}, URN = {urn:nbn:de:0030-drops-36689}, doi = {10.4230/LIPIcs.CSL.2012.122}, annote = {Keywords: Constraint satisfaction problems, universal algebra, model theory, Ram- sey theory, temporal reasoning, computational complexity} }
Feedback for Dagstuhl Publishing