Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Antoine Mottet, Tomáš Nagy, and Michael Pinsker. An Order out of Nowhere: A New Algorithm for Infinite-Domain {CSP}s. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 148:1-148:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mottet_et_al:LIPIcs.ICALP.2024.148, author = {Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael}, title = {{An Order out of Nowhere: A New Algorithm for Infinite-Domain \{CSP\}s}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {148:1--148:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.148}, URN = {urn:nbn:de:0030-drops-202912}, doi = {10.4230/LIPIcs.ICALP.2024.148}, annote = {Keywords: Constraint Satisfaction Problems, Hypergraphs, Polymorphisms} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Jakub Rydval. Homogeneity and Homogenizability: Hard Problems for the Logic SNP. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 150:1-150:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{rydval:LIPIcs.ICALP.2024.150, author = {Rydval, Jakub}, title = {{Homogeneity and Homogenizability: Hard Problems for the Logic SNP}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {150:1--150:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.150}, URN = {urn:nbn:de:0030-drops-202939}, doi = {10.4230/LIPIcs.ICALP.2024.150}, annote = {Keywords: constraint satisfaction problems, finitely bounded, homogeneous, amalgamation property, universal, SNP, homogenizable} }
Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Antoine Mottet. Promise and Infinite-Domain Constraint Satisfaction. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mottet:LIPIcs.CSL.2024.41, author = {Mottet, Antoine}, title = {{Promise and Infinite-Domain Constraint Satisfaction}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {41:1--41:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.41}, URN = {urn:nbn:de:0030-drops-196842}, doi = {10.4230/LIPIcs.CSL.2024.41}, annote = {Keywords: promise constraint satisfaction problems, polymorphisms, homogeneous structures, first-order logic} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Wojciech Czerwiński, Antoine Mottet, and Karin Quaas. New Techniques for Universality in Unambiguous Register Automata. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 129:1-129:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{czerwinski_et_al:LIPIcs.ICALP.2021.129, author = {Czerwi\'{n}ski, Wojciech and Mottet, Antoine and Quaas, Karin}, title = {{New Techniques for Universality in Unambiguous Register Automata}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {129:1--129:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.129}, URN = {urn:nbn:de:0030-drops-141983}, doi = {10.4230/LIPIcs.ICALP.2021.129}, annote = {Keywords: Register Automata, Data Languages, Unambiguity, Unambiguous, Universality, Containment, Language Inclusion, Equivalence} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Antoine Mottet, Tomáš Nagy, Michael Pinsker, and Michał Wrona. Smooth Approximations and Relational Width Collapses. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 138:1-138:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{mottet_et_al:LIPIcs.ICALP.2021.138, author = {Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael and Wrona, Micha{\l}}, title = {{Smooth Approximations and Relational Width Collapses}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {138:1--138:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.138}, URN = {urn:nbn:de:0030-drops-142075}, doi = {10.4230/LIPIcs.ICALP.2021.138}, annote = {Keywords: local consistency, bounded width, constraint satisfaction problems, polymorphisms, smooth approximations} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. Hrushovski’s Encoding and ω-Categorical CSP Monsters. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 131:1-131:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gillibert_et_al:LIPIcs.ICALP.2020.131, author = {Gillibert, Pierre and Jonu\v{s}as, Julius and Kompatscher, Michael and Mottet, Antoine and Pinsker, Michael}, title = {{Hrushovski’s Encoding and \omega-Categorical CSP Monsters}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {131:1--131:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.131}, URN = {urn:nbn:de:0030-drops-125387}, doi = {10.4230/LIPIcs.ICALP.2020.131}, annote = {Keywords: Constraint satisfaction problem, complexity, polymorphism, pointwise convergence topology, height 1 identity, \omega-categoricity, orbit growth} }
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.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 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Antoine Mottet and Karin Quaas. The Containment Problem for Unambiguous Register Automata. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{mottet_et_al:LIPIcs.STACS.2019.53, author = {Mottet, Antoine and Quaas, Karin}, title = {{The Containment Problem for Unambiguous Register Automata}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {53:1--53:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.53}, URN = {urn:nbn:de:0030-drops-102926}, doi = {10.4230/LIPIcs.STACS.2019.53}, annote = {Keywords: Data words, Register automata, Unambiguous Automata, Containment Problem, Language Inclusion Problem} }
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.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} }