LIPIcs, Volume 138
MFCS 2019, August 26-30, 2019, Aachen, Germany
Editors: Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen
Published in: Dagstuhl Reports, Volume 13, Issue 6 (2024)
Sebastian Junges, Joost-Pieter Katoen, Scott Sanner, Guy Van den Broeck, and Bahare Salmani. Scalable Analysis of Probabilistic Models and Programs (Dagstuhl Seminar 23241). In Dagstuhl Reports, Volume 13, Issue 6, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{junges_et_al:DagRep.13.6.1, author = {Junges, Sebastian and Katoen, Joost-Pieter and Sanner, Scott and Van den Broeck, Guy and Salmani, Bahare}, title = {{Scalable Analysis of Probabilistic Models and Programs (Dagstuhl Seminar 23241)}}, pages = {1--21}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2024}, volume = {13}, number = {6}, editor = {Junges, Sebastian and Katoen, Joost-Pieter and Sanner, Scott and Van den Broeck, Guy and Salmani, Bahare}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.6.1}, URN = {urn:nbn:de:0030-drops-196362}, doi = {10.4230/DagRep.13.6.1}, annote = {Keywords: model counting, probabilistic inference, probabilistic model checking, probabilistic planning, probabilistic programs} }
Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)
Ira Fesefeldt, Joost-Pieter Katoen, and Thomas Noll. Towards Concurrent Quantitative Separation Logic. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fesefeldt_et_al:LIPIcs.CONCUR.2022.25, author = {Fesefeldt, Ira and Katoen, Joost-Pieter and Noll, Thomas}, title = {{Towards Concurrent Quantitative Separation Logic}}, booktitle = {33rd International Conference on Concurrency Theory (CONCUR 2022)}, pages = {25:1--25:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-246-4}, ISSN = {1868-8969}, year = {2022}, volume = {243}, editor = {Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.25}, URN = {urn:nbn:de:0030-drops-170881}, doi = {10.4230/LIPIcs.CONCUR.2022.25}, annote = {Keywords: Randomization, Pointers, Heap-Manipulating, Separation Logic, Concurrency} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Rupak Majumdar, Mahmoud Salamati, and Sadegh Soudjani. On Decidability of Time-Bounded Reachability in CTMDPs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 133:1-133:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{majumdar_et_al:LIPIcs.ICALP.2020.133, author = {Majumdar, Rupak and Salamati, Mahmoud and Soudjani, Sadegh}, title = {{On Decidability of Time-Bounded Reachability in CTMDPs}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {133:1--133:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.133}, URN = {urn:nbn:de:0030-drops-125408}, doi = {10.4230/LIPIcs.ICALP.2020.133}, annote = {Keywords: CTMDP, Time bounded reachability, Continuous Skolem Problem, Schanuel’s Conjecture} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Proceedings{rossmanith_et_al:LIPIcs.MFCS.2019, title = {{LIPIcs, Volume 138, MFCS'19, Complete Volume}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019}, URN = {urn:nbn:de:0030-drops-112092}, doi = {10.4230/LIPIcs.MFCS.2019}, annote = {Keywords: Theory of computation} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{rossmanith_et_al:LIPIcs.MFCS.2019.0, author = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.0}, URN = {urn:nbn:de:0030-drops-109444}, doi = {10.4230/LIPIcs.MFCS.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Mohammad Abdulaziz, Kurt Mehlhorn, and Tobias Nipkow. Trustworthy Graph Algorithms (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{abdulaziz_et_al:LIPIcs.MFCS.2019.1, author = {Abdulaziz, Mohammad and Mehlhorn, Kurt and Nipkow, Tobias}, title = {{Trustworthy Graph Algorithms}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {1:1--1:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.1}, URN = {urn:nbn:de:0030-drops-109456}, doi = {10.4230/LIPIcs.MFCS.2019.1}, annote = {Keywords: graph algorithms, formal correct proofs, Isabelle, LEDA, certifying algorithms} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Alexandra Silva. Guarded Kleene Algebra with Tests: Verification of Uninterpreted Programs in Nearly Linear Time (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{silva:LIPIcs.MFCS.2019.2, author = {Silva, Alexandra}, title = {{Guarded Kleene Algebra with Tests: Verification of Uninterpreted Programs in Nearly Linear Time}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.2}, URN = {urn:nbn:de:0030-drops-109462}, doi = {10.4230/LIPIcs.MFCS.2019.2}, annote = {Keywords: Kleene algebra, verification, decision procedures} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Daniel Lokshtanov. Picking Random Vertices (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lokshtanov:LIPIcs.MFCS.2019.3, author = {Lokshtanov, Daniel}, title = {{Picking Random Vertices}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.3}, URN = {urn:nbn:de:0030-drops-109478}, doi = {10.4230/LIPIcs.MFCS.2019.3}, annote = {Keywords: Graph Algorithm} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Telikepalli Kavitha. Popular Matchings: Good, Bad, and Mixed (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kavitha:LIPIcs.MFCS.2019.4, author = {Kavitha, Telikepalli}, title = {{Popular Matchings: Good, Bad, and Mixed}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {4:1--4:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.4}, URN = {urn:nbn:de:0030-drops-109489}, doi = {10.4230/LIPIcs.MFCS.2019.4}, annote = {Keywords: Matchings under preferences, Algorithms, NP-Hardness} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Jérôme Leroux. Petri Net Reachability Problem (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 5:1-5:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{leroux:LIPIcs.MFCS.2019.5, author = {Leroux, J\'{e}r\^{o}me}, title = {{Petri Net Reachability Problem}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {5:1--5:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.5}, URN = {urn:nbn:de:0030-drops-109493}, doi = {10.4230/LIPIcs.MFCS.2019.5}, annote = {Keywords: Petri net, Reachability problem, Formal verification, Concurrency} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Marcin Bienkowski and Hsiang-Hsuan Liu. An Improved Online Algorithm for the Traveling Repairperson Problem on a Line. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bienkowski_et_al:LIPIcs.MFCS.2019.6, author = {Bienkowski, Marcin and Liu, Hsiang-Hsuan}, title = {{An Improved Online Algorithm for the Traveling Repairperson Problem on a Line}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {6:1--6:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.6}, URN = {urn:nbn:de:0030-drops-109503}, doi = {10.4230/LIPIcs.MFCS.2019.6}, annote = {Keywords: traveling repairperson problem, competitive analysis, minimizing completion time, factor-revealing LP} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Magnús M. Halldórsson and Murilo Santos de Lima. Query-Competitive Sorting with Uncertainty. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{halldorsson_et_al:LIPIcs.MFCS.2019.7, author = {Halld\'{o}rsson, Magn\'{u}s M. and de Lima, Murilo Santos}, title = {{Query-Competitive Sorting with Uncertainty}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.7}, URN = {urn:nbn:de:0030-drops-109519}, doi = {10.4230/LIPIcs.MFCS.2019.7}, annote = {Keywords: online algorithms, sorting, randomized algorithms, advice complexity, threshold tolerance graphs} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż, and Elias Koutsoupias. Better Bounds for Online Line Chasing. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bienkowski_et_al:LIPIcs.MFCS.2019.8, author = {Bienkowski, Marcin and Byrka, Jaros{\l}aw and Chrobak, Marek and Coester, Christian and Je\.{z}, {\L}ukasz and Koutsoupias, Elias}, title = {{Better Bounds for Online Line Chasing}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {8:1--8:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.8}, URN = {urn:nbn:de:0030-drops-109521}, doi = {10.4230/LIPIcs.MFCS.2019.8}, annote = {Keywords: convex body chasing, line chasing, competitive analysis} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Patricia Bouyer and Nathan Thomasset. Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bouyer_et_al:LIPIcs.MFCS.2019.9, author = {Bouyer, Patricia and Thomasset, Nathan}, title = {{Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.9}, URN = {urn:nbn:de:0030-drops-109532}, doi = {10.4230/LIPIcs.MFCS.2019.9}, annote = {Keywords: Multiplayer games, Nash equilibria, partial information} }
Feedback for Dagstuhl Publishing