Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Balder ten Cate. Craig Interpolation for Decidable Fragments of First-Order Logic (Invited Talk). In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{tencate:LIPIcs.CSL.2024.2, author = {ten Cate, Balder}, title = {{Craig Interpolation for Decidable Fragments of First-Order Logic}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {2:1--2:2}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.2}, URN = {urn:nbn:de:0030-drops-196488}, doi = {10.4230/LIPIcs.CSL.2024.2}, annote = {Keywords: First-Order Logic, Decidable Fragments, Craig Interpolation} }
Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Moritz Lichter, Benedikt Pago, and Tim Seppelt. Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lichter_et_al:LIPIcs.CSL.2024.36, author = {Lichter, Moritz and Pago, Benedikt and Seppelt, Tim}, title = {{Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {36:1--36: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.36}, URN = {urn:nbn:de:0030-drops-196799}, doi = {10.4230/LIPIcs.CSL.2024.36}, annote = {Keywords: finite model theory, graph isomorphism, linear-algebraic logic, homomorphism indistinguishability, game comonads, invertible-map equivalence} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Benedikt Pago. Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{pago:LIPIcs.MFCS.2023.73, author = {Pago, Benedikt}, title = {{Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {73:1--73:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.73}, URN = {urn:nbn:de:0030-drops-186077}, doi = {10.4230/LIPIcs.MFCS.2023.73}, annote = {Keywords: logic in computer science, finite model theory, descriptive complexity, symmetric computation, symmetric circuits, graph isomorphism} }
Published in: LIPIcs, Volume 269, 28th International Conference on Types for Proofs and Programs (TYPES 2022)
Kobe Wullaert, Ralph Matthes, and Benedikt Ahrens. Univalent Monoidal Categories. In 28th International Conference on Types for Proofs and Programs (TYPES 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 269, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{wullaert_et_al:LIPIcs.TYPES.2022.15, author = {Wullaert, Kobe and Matthes, Ralph and Ahrens, Benedikt}, title = {{Univalent Monoidal Categories}}, booktitle = {28th International Conference on Types for Proofs and Programs (TYPES 2022)}, pages = {15:1--15:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-285-3}, ISSN = {1868-8969}, year = {2023}, volume = {269}, editor = {Kesner, Delia and P\'{e}drot, Pierre-Marie}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TYPES.2022.15}, URN = {urn:nbn:de:0030-drops-184580}, doi = {10.4230/LIPIcs.TYPES.2022.15}, annote = {Keywords: Univalence, Monoidal categories, Rezk completion, Displayed (bi)categories, Proof assistant Coq, UniMath library} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Michael Benedikt, Dmitry Chistikov, and Alessio Mansutti. The Complexity of Presburger Arithmetic with Power or Powers. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 112:1-112:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{benedikt_et_al:LIPIcs.ICALP.2023.112, author = {Benedikt, Michael and Chistikov, Dmitry and Mansutti, Alessio}, title = {{The Complexity of Presburger Arithmetic with Power or Powers}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {112:1--112:18}, 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.112}, URN = {urn:nbn:de:0030-drops-181641}, doi = {10.4230/LIPIcs.ICALP.2023.112}, annote = {Keywords: arithmetic theories, exponentiation, decision procedures} }
Published in: LIPIcs, Volume 260, 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)
Niels van der Weide. The Formal Theory of Monads, Univalently. In 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 260, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{vanderweide:LIPIcs.FSCD.2023.6, author = {van der Weide, Niels}, title = {{The Formal Theory of Monads, Univalently}}, booktitle = {8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)}, pages = {6:1--6:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-277-8}, ISSN = {1868-8969}, year = {2023}, volume = {260}, editor = {Gaboardi, Marco and van Raamsdonk, Femke}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2023.6}, URN = {urn:nbn:de:0030-drops-179904}, doi = {10.4230/LIPIcs.FSCD.2023.6}, annote = {Keywords: bicategory theory, univalent foundations, formalization, monads, Coq} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud. Computing a Dirichlet Domain for a Hyperbolic Surface. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{despre_et_al:LIPIcs.SoCG.2023.27, author = {Despr\'{e}, Vincent and Kolbe, Benedikt and Parlier, Hugo and Teillaud, Monique}, title = {{Computing a Dirichlet Domain for a Hyperbolic Surface}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.27}, URN = {urn:nbn:de:0030-drops-178771}, doi = {10.4230/LIPIcs.SoCG.2023.27}, annote = {Keywords: Hyperbolic geometry, Topology, Voronoi diagram, Algorithm} }
Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Benedikt Pago. Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{pago:LIPIcs.CSL.2023.31, author = {Pago, Benedikt}, title = {{Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus}}, booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)}, pages = {31:1--31:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-264-8}, ISSN = {1868-8969}, year = {2023}, volume = {252}, editor = {Klin, Bartek and Pimentel, Elaine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.31}, URN = {urn:nbn:de:0030-drops-174923}, doi = {10.4230/LIPIcs.CSL.2023.31}, annote = {Keywords: finite model theory, proof complexity, graph isomorphism} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Ulrich Bauer, Håvard Bakke Bjerkevik, and Benedikt Fluhr. Quasi-Universality of Reeb Graph Distances. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bauer_et_al:LIPIcs.SoCG.2022.14, author = {Bauer, Ulrich and Bjerkevik, H\r{a}vard Bakke and Fluhr, Benedikt}, title = {{Quasi-Universality of Reeb Graph Distances}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {14:1--14:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.14}, URN = {urn:nbn:de:0030-drops-160221}, doi = {10.4230/LIPIcs.SoCG.2022.14}, annote = {Keywords: Reeb graphs, contour trees, merge trees, distances, universality, interleaving distance, functional distortion distance, functional contortion distance} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Benedikt Bollig, Arnaud Sangnier, and Olivier Stietel. Local First-Order Logic with Two Data Values. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bollig_et_al:LIPIcs.FSTTCS.2021.39, author = {Bollig, Benedikt and Sangnier, Arnaud and Stietel, Olivier}, title = {{Local First-Order Logic with Two Data Values}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.39}, URN = {urn:nbn:de:0030-drops-155508}, doi = {10.4230/LIPIcs.FSTTCS.2021.39}, annote = {Keywords: first-order logic, data values, specification of distributed algorithms} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Anuj Dawar and Danny Vagnozzi. On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dawar_et_al:LIPIcs.MFCS.2021.37, author = {Dawar, Anuj and Vagnozzi, Danny}, title = {{On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {37:1--37:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.37}, URN = {urn:nbn:de:0030-drops-144774}, doi = {10.4230/LIPIcs.MFCS.2021.37}, annote = {Keywords: Graph isomorphism, proof complexity, invertible map tests} }
Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)
Benedikt Bollig, Cinzia Di Giusto, Alain Finkel, Laetitia Laversa, Etienne Lozes, and Amrita Suresh. A Unifying Framework for Deciding Synchronizability. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bollig_et_al:LIPIcs.CONCUR.2021.14, author = {Bollig, Benedikt and Di Giusto, Cinzia and Finkel, Alain and Laversa, Laetitia and Lozes, Etienne and Suresh, Amrita}, title = {{A Unifying Framework for Deciding Synchronizability}}, booktitle = {32nd International Conference on Concurrency Theory (CONCUR 2021)}, pages = {14:1--14:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-203-7}, ISSN = {1868-8969}, year = {2021}, volume = {203}, editor = {Haddad, Serge and Varacca, Daniele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.14}, URN = {urn:nbn:de:0030-drops-143917}, doi = {10.4230/LIPIcs.CONCUR.2021.14}, annote = {Keywords: communicating finite-state machines, message sequence charts, synchronizability, MSO logic, special tree-width} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Stefan Göller and Mathieu Hilaire. Reachability in Two-Parametric Timed Automata with One Parameter Is EXPSPACE-Complete. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{goller_et_al:LIPIcs.STACS.2021.36, author = {G\"{o}ller, Stefan and Hilaire, Mathieu}, title = {{Reachability in Two-Parametric Timed Automata with One Parameter Is EXPSPACE-Complete}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {36:1--36:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.36}, URN = {urn:nbn:de:0030-drops-136817}, doi = {10.4230/LIPIcs.STACS.2021.36}, annote = {Keywords: Parametric Timed Automata, Computational Complexity, Reachability} }
Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Benedikt Bollig, Fedor Ryabinin, and Arnaud Sangnier. Reachability in Distributed Memory Automata. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bollig_et_al:LIPIcs.CSL.2021.13, author = {Bollig, Benedikt and Ryabinin, Fedor and Sangnier, Arnaud}, title = {{Reachability in Distributed Memory Automata}}, booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)}, pages = {13:1--13:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-175-7}, ISSN = {1868-8969}, year = {2021}, volume = {183}, editor = {Baier, Christel and Goubault-Larrecq, Jean}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.13}, URN = {urn:nbn:de:0030-drops-134472}, doi = {10.4230/LIPIcs.CSL.2021.13}, annote = {Keywords: Distributed algorithms, Atomic snapshot objects, Register automata, Reachability} }
Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Benedikt Pago. Choiceless Computation and Symmetry: Limitations of Definability. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{pago:LIPIcs.CSL.2021.33, author = {Pago, Benedikt}, title = {{Choiceless Computation and Symmetry: Limitations of Definability}}, booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)}, pages = {33:1--33:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-175-7}, ISSN = {1868-8969}, year = {2021}, volume = {183}, editor = {Baier, Christel and Goubault-Larrecq, Jean}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.33}, URN = {urn:nbn:de:0030-drops-134673}, doi = {10.4230/LIPIcs.CSL.2021.33}, annote = {Keywords: finite model theory, descriptive complexity, choiceless computation, symmetries of combinatorial objects} }
Feedback for Dagstuhl Publishing