Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Evan Chang, Neel Kolhe, and Youngtak Sohn. Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 47:1-47:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chang_et_al:LIPIcs.APPROX/RANDOM.2024.47, author = {Chang, Evan and Kolhe, Neel and Sohn, Youngtak}, title = {{Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {47:1--47:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.47}, URN = {urn:nbn:de:0030-drops-210402}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.47}, annote = {Keywords: Random constraint satisfaction problem, replica symmetry breaking, interpolation bound} }
Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Lorenzo Ceragioli, Fabio Gadducci, Giuseppe Lomurno, and Gabriele Tedeschi. Effect Semantics for Quantum Process Calculi. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ceragioli_et_al:LIPIcs.CONCUR.2024.16, author = {Ceragioli, Lorenzo and Gadducci, Fabio and Lomurno, Giuseppe and Tedeschi, Gabriele}, title = {{Effect Semantics for Quantum Process Calculi}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {16:1--16:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak 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.CONCUR.2024.16}, URN = {urn:nbn:de:0030-drops-207886}, doi = {10.4230/LIPIcs.CONCUR.2024.16}, annote = {Keywords: Quantum process calculi, probabilistic LTSs, effect LTSs} }
Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Dmitry Chistikov, Jérôme Leroux, Henry Sinclair-Banks, and Nicolas Waldburger. Invariants for One-Counter Automata with Disequality Tests. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chistikov_et_al:LIPIcs.CONCUR.2024.17, author = {Chistikov, Dmitry and Leroux, J\'{e}r\^{o}me and Sinclair-Banks, Henry and Waldburger, Nicolas}, title = {{Invariants for One-Counter Automata with Disequality Tests}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {17:1--17:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak 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.CONCUR.2024.17}, URN = {urn:nbn:de:0030-drops-207898}, doi = {10.4230/LIPIcs.CONCUR.2024.17}, annote = {Keywords: Inductive invariant, Vector addition system, One-counter automaton} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Isolde Adler and Eva Fluck. Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{adler_et_al:LIPIcs.MFCS.2024.6, author = {Adler, Isolde and Fluck, Eva}, title = {{Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.6}, URN = {urn:nbn:de:0030-drops-205621}, doi = {10.4230/LIPIcs.MFCS.2024.6}, annote = {Keywords: tree decompositions, treewidth, treedepth, cops-and-robber game, monotonicity, homomorphism distinguishing closure} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Tim Seppelt. An Algorithmic Meta Theorem for Homomorphism Indistinguishability. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 82:1-82:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{seppelt:LIPIcs.MFCS.2024.82, author = {Seppelt, Tim}, title = {{An Algorithmic Meta Theorem for Homomorphism Indistinguishability}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {82:1--82:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.82}, URN = {urn:nbn:de:0030-drops-206387}, doi = {10.4230/LIPIcs.MFCS.2024.82}, annote = {Keywords: homomorphism indistinguishability, graph homomorphism, graph minor, recognisability, randomised algorithm, Courcelle’s Theorem} }
Published in: LIPIcs, Volume 303, 29th International Conference on Types for Proofs and Programs (TYPES 2023)
Matthias Eberl. A Reflection Principle for Potential Infinite Models of Type Theory. In 29th International Conference on Types for Proofs and Programs (TYPES 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 303, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{eberl:LIPIcs.TYPES.2023.6, author = {Eberl, Matthias}, title = {{A Reflection Principle for Potential Infinite Models of Type Theory}}, booktitle = {29th International Conference on Types for Proofs and Programs (TYPES 2023)}, pages = {6:1--6:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-332-4}, ISSN = {1868-8969}, year = {2024}, volume = {303}, editor = {Kesner, Delia and Reyes, Eduardo Hermo and van den Berg, Benno}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TYPES.2023.6}, URN = {urn:nbn:de:0030-drops-204845}, doi = {10.4230/LIPIcs.TYPES.2023.6}, annote = {Keywords: Indefinite extensibility, Potential infinite, Reflection principle} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
Pablo Donato. The Flower Calculus. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{donato:LIPIcs.FSCD.2024.5, author = {Donato, Pablo}, title = {{The Flower Calculus}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {5:1--5:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-323-2}, ISSN = {1868-8969}, year = {2024}, volume = {299}, editor = {Rehof, Jakob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.5}, URN = {urn:nbn:de:0030-drops-203343}, doi = {10.4230/LIPIcs.FSCD.2024.5}, annote = {Keywords: deep inference, graphical calculi, existential graphs, intuitionistic logic, Kripke semantics, cut-elimination} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
Junyoung Jang, Sophia Roshal, Frank Pfenning, and Brigitte Pientka. Adjoint Natural Deduction. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jang_et_al:LIPIcs.FSCD.2024.15, author = {Jang, Junyoung and Roshal, Sophia and Pfenning, Frank and Pientka, Brigitte}, title = {{Adjoint Natural Deduction}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {15:1--15:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-323-2}, ISSN = {1868-8969}, year = {2024}, volume = {299}, editor = {Rehof, Jakob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.15}, URN = {urn:nbn:de:0030-drops-203441}, doi = {10.4230/LIPIcs.FSCD.2024.15}, annote = {Keywords: Substructural Logic, Type Systems, Functional Programming} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
Beniamino Accattoli and Claudio Sacerdoti Coen. IMELL Cut Elimination with Linear Overhead. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 24:1-24:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{accattoli_et_al:LIPIcs.FSCD.2024.24, author = {Accattoli, Beniamino and Sacerdoti Coen, Claudio}, title = {{IMELL Cut Elimination with Linear Overhead}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {24:1--24:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-323-2}, ISSN = {1868-8969}, year = {2024}, volume = {299}, editor = {Rehof, Jakob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.24}, URN = {urn:nbn:de:0030-drops-203539}, doi = {10.4230/LIPIcs.FSCD.2024.24}, annote = {Keywords: Lambda calculus, linear logic, abstract machines} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
Samson Abramsky, Şerban-Ion Cercelescu, and Carmen-Maria Constantin. Commutation Groups and State-Independent Contextuality. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abramsky_et_al:LIPIcs.FSCD.2024.28, author = {Abramsky, Samson and Cercelescu, \c{S}erban-Ion and Constantin, Carmen-Maria}, title = {{Commutation Groups and State-Independent Contextuality}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {28:1--28:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-323-2}, ISSN = {1868-8969}, year = {2024}, volume = {299}, editor = {Rehof, Jakob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.28}, URN = {urn:nbn:de:0030-drops-203572}, doi = {10.4230/LIPIcs.FSCD.2024.28}, annote = {Keywords: Contextuality, state-independence, quantum mechanics, Pauli group, group presentations, unitary representations} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sophia Heimann, Hung P. Hoang, and Stefan Hougardy. The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 84:1-84:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{heimann_et_al:LIPIcs.ICALP.2024.84, author = {Heimann, Sophia and Hoang, Hung P. and Hougardy, Stefan}, title = {{The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {84:1--84: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.84}, URN = {urn:nbn:de:0030-drops-202270}, doi = {10.4230/LIPIcs.ICALP.2024.84}, annote = {Keywords: Traveling Salesman Problem, k-Opt algorithm, PLS-completeness} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Mikołaj Bojańczyk, Lê Thành Dũng (Tito) Nguyễn, and Rafał Stefański. Function Spaces for Orbit-Finite Sets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 130:1-130:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bojanczyk_et_al:LIPIcs.ICALP.2024.130, author = {Boja\'{n}czyk, Miko{\l}aj and Nguy\~{ê}n, L\^{e} Th\`{a}nh D\~{u}ng (Tito) and Stefa\'{n}ski, Rafa{\l}}, title = {{Function Spaces for Orbit-Finite Sets}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {130:1--130: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.130}, URN = {urn:nbn:de:0030-drops-202730}, doi = {10.4230/LIPIcs.ICALP.2024.130}, annote = {Keywords: Orbit-finite sets, automata, linear types, game semantics} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Arnaud Carayol and Lucien Charamond. The Structure of Trees in the Pushdown Hierarchy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 131:1-131:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{carayol_et_al:LIPIcs.ICALP.2024.131, author = {Carayol, Arnaud and Charamond, Lucien}, title = {{The Structure of Trees in the Pushdown Hierarchy}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {131:1--131: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.131}, URN = {urn:nbn:de:0030-drops-202749}, doi = {10.4230/LIPIcs.ICALP.2024.131}, annote = {Keywords: Pushdown hierarchy, Monadic second-order logic, Automatic numbers} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yuxi Fu, Qizhe Yang, and Yangluo Zheng. Improved Algorithm for Reachability in d-VASS. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 136:1-136:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fu_et_al:LIPIcs.ICALP.2024.136, author = {Fu, Yuxi and Yang, Qizhe and Zheng, Yangluo}, title = {{Improved Algorithm for Reachability in d-VASS}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {136:1--136: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.136}, URN = {urn:nbn:de:0030-drops-202799}, doi = {10.4230/LIPIcs.ICALP.2024.136}, annote = {Keywords: Petri net, vector addition system, reachability} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Samson Abramsky and Dan Marsden. Comonadic semantics for hybrid logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{abramsky_et_al:LIPIcs.MFCS.2022.7, author = {Abramsky, Samson and Marsden, Dan}, title = {{Comonadic semantics for hybrid logic}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {7:1--7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert 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.MFCS.2022.7}, URN = {urn:nbn:de:0030-drops-168055}, doi = {10.4230/LIPIcs.MFCS.2022.7}, annote = {Keywords: comonads, model comparison games, semantic characterizations, hybrid logic, bounded fragment} }
Feedback for Dagstuhl Publishing