Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Mario Grobler, Leif Sabellek, and Sebastian Siebertz. Remarks on Parikh-Recognizable Omega-languages. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{grobler_et_al:LIPIcs.CSL.2024.31, author = {Grobler, Mario and Sabellek, Leif and Siebertz, Sebastian}, title = {{Remarks on Parikh-Recognizable Omega-languages}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {31:1--31:21}, 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.31}, URN = {urn:nbn:de:0030-drops-196743}, doi = {10.4230/LIPIcs.CSL.2024.31}, annote = {Keywords: Parikh automata, blind counter machines, infinite words, B\"{u}chi’s theorem} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Gerth Stølting Brodal and Sebastian Wild. Funnelselect: Cache-Oblivious Multiple Selection. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{brodal_et_al:LIPIcs.ESA.2023.25, author = {Brodal, Gerth St{\o}lting and Wild, Sebastian}, title = {{Funnelselect: Cache-Oblivious Multiple Selection}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {25:1--25:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.25}, URN = {urn:nbn:de:0030-drops-186789}, doi = {10.4230/LIPIcs.ESA.2023.25}, annote = {Keywords: Multiple selection, cache-oblivious algorithm, randomized algorithm, entropy bounds} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk. Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 125:1-125:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dreier_et_al:LIPIcs.ICALP.2023.125, author = {Dreier, Jan and M\"{a}hlmann, Nikolas and Siebertz, Sebastian and Toru\'{n}czyk, Szymon}, title = {{Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {125:1--125: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.125}, URN = {urn:nbn:de:0030-drops-181779}, doi = {10.4230/LIPIcs.ICALP.2023.125}, annote = {Keywords: stability, NIP, combinatorial characterization, first-order model checking} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk. Flipper Games for Monadically Stable Graph Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 128:1-128:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2023.128, author = {Gajarsk\'{y}, Jakub and M\"{a}hlmann, Nikolas and McCarty, Rose and Ohlmann, Pierre and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Siebertz, Sebastian and Soko{\l}owski, Marek and Toru\'{n}czyk, Szymon}, title = {{Flipper Games for Monadically Stable Graph Classes}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {128:1--128:16}, 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.128}, URN = {urn:nbn:de:0030-drops-181804}, doi = {10.4230/LIPIcs.ICALP.2023.128}, annote = {Keywords: Stability theory, structural graph theory, games} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Susanne Albers and Sebastian Schubert. Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{albers_et_al:LIPIcs.ESA.2022.4, author = {Albers, Susanne and Schubert, Sebastian}, title = {{Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {4:1--4:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.4}, URN = {urn:nbn:de:0030-drops-169420}, doi = {10.4230/LIPIcs.ESA.2022.4}, annote = {Keywords: online algorithms, deterministic algorithms, primal-dual analysis, b-matching, bounded-degree graph, variable vertex capacities, unweighted matching, vertex-weighted matching} }
Published in: Dagstuhl Reports, Volume 11, Issue 6 (2021)
Sebastian Böcker, Rebekah Gundry, Lennart Martens, and Magnus Palmblad. Computational Proteomics (Dagstuhl Seminar 21271). In Dagstuhl Reports, Volume 11, Issue 6, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Article{bocker_et_al:DagRep.11.6.1, author = {B\"{o}cker, Sebastian and Gundry, Rebekah and Martens, Lennart and Palmblad, Magnus}, title = {{Computational Proteomics (Dagstuhl Seminar 21271)}}, pages = {1--13}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2021}, volume = {11}, number = {6}, editor = {B\"{o}cker, Sebastian and Gundry, Rebekah and Martens, Lennart and Palmblad, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.6.1}, URN = {urn:nbn:de:0030-drops-155775}, doi = {10.4230/DagRep.11.6.1}, annote = {Keywords: bioinformatics, computational mass spectrometry, machine learning, proteomics} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Susanne Albers and Sebastian Schubert. Optimal Algorithms for Online b-Matching with Variable Vertex Capacities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{albers_et_al:LIPIcs.APPROX/RANDOM.2021.2, author = {Albers, Susanne and Schubert, Sebastian}, title = {{Optimal Algorithms for Online b-Matching with Variable Vertex Capacities}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {2:1--2:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.2}, URN = {urn:nbn:de:0030-drops-146957}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.2}, annote = {Keywords: Online algorithms, primal-dual analysis, configuration LP, b-matching, variable vertex capacities, unweighted matching, vertex-weighted matching} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Nikolas Mählmann, Sebastian Siebertz, and Alexandre Vigny. Recursive Backdoors for SAT. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 73:1-73:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{mahlmann_et_al:LIPIcs.MFCS.2021.73, author = {M\"{a}hlmann, Nikolas and Siebertz, Sebastian and Vigny, Alexandre}, title = {{Recursive Backdoors for SAT}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {73:1--73:18}, 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.73}, URN = {urn:nbn:de:0030-drops-145138}, doi = {10.4230/LIPIcs.MFCS.2021.73}, annote = {Keywords: Propositional satisfiability SAT, Backdoors, Parameterized Algorithms} }
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 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Michael B. Cohen, Aaron Sidford, and Kevin Tian. Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohen_et_al:LIPIcs.ITCS.2021.62, author = {Cohen, Michael B. and Sidford, Aaron and Tian, Kevin}, title = {{Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {62:1--62:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.62}, URN = {urn:nbn:de:0030-drops-136011}, doi = {10.4230/LIPIcs.ITCS.2021.62}, annote = {Keywords: Variational inequalities, minimax optimization, acceleration, 𝓁\underline∞ regression} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Stefan Dziembowski, Grzegorz Fabiański, Sebastian Faust, and Siavash Riahi. Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 72:1-72:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dziembowski_et_al:LIPIcs.ITCS.2021.72, author = {Dziembowski, Stefan and Fabia\'{n}ski, Grzegorz and Faust, Sebastian and Riahi, Siavash}, title = {{Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {72:1--72:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.72}, URN = {urn:nbn:de:0030-drops-136113}, doi = {10.4230/LIPIcs.ITCS.2021.72}, annote = {Keywords: blockchain, lower bounds, off-chain protocol, commit chain, plasma} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Sebastian Maneth and Helmut Seidl. When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 134:1-134:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{maneth_et_al:LIPIcs.ICALP.2020.134, author = {Maneth, Sebastian and Seidl, Helmut}, title = {{When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {134:1--134:18}, 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.134}, URN = {urn:nbn:de:0030-drops-125416}, doi = {10.4230/LIPIcs.ICALP.2020.134}, annote = {Keywords: Top-Down Tree Transducers, Earliest Transformation, Linear Transducers, Uniform-copying Transucers, Removal of Look-ahead, Removal of Inspection} }
Published in: Dagstuhl Reports, Volume 10, Issue 1 (2020)
Sebastian Böcker, Corey Broeckling, Emma Schymanski, and Nicola Zamboni. Computational Metabolomics: From Cheminformatics to Machine Learning (Dagstuhl Seminar 20051). In Dagstuhl Reports, Volume 10, Issue 1, pp. 144-159, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@Article{bocker_et_al:DagRep.10.1.144, author = {B\"{o}cker, Sebastian and Broeckling, Corey and Schymanski, Emma and Zamboni, Nicola}, title = {{Computational Metabolomics: From Cheminformatics to Machine Learning (Dagstuhl Seminar 20051)}}, pages = {144--159}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2020}, volume = {10}, number = {1}, editor = {B\"{o}cker, Sebastian and Broeckling, Corey and Schymanski, Emma and Zamboni, Nicola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.10.1.144}, URN = {urn:nbn:de:0030-drops-124036}, doi = {10.4230/DagRep.10.1.144}, annote = {Keywords: bioinformatics, chemoinformatics, computational mass spectrometry, computational metabolomics, machine learning} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Emanuel Kieroński. One-Dimensional Guarded Fragments. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kieronski:LIPIcs.MFCS.2019.16, author = {Kiero\'{n}ski, Emanuel}, title = {{One-Dimensional Guarded Fragments}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {16:1--16: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.16}, URN = {urn:nbn:de:0030-drops-109608}, doi = {10.4230/LIPIcs.MFCS.2019.16}, annote = {Keywords: guarded fragment, two-variable logic, satisfiability, finite model property} }
Published in: LIPIcs, Volume 113, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)
Kai Dührkop, Marie A. Lataretu, W. Timothy J. White, and Sebastian Böcker. Heuristic Algorithms for the Maximum Colorful Subtree Problem. In 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 113, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{duhrkop_et_al:LIPIcs.WABI.2018.23, author = {D\"{u}hrkop, Kai and Lataretu, Marie A. and White, W. Timothy J. and B\"{o}cker, Sebastian}, title = {{Heuristic Algorithms for the Maximum Colorful Subtree Problem}}, booktitle = {18th International Workshop on Algorithms in Bioinformatics (WABI 2018)}, pages = {23:1--23:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-082-8}, ISSN = {1868-8969}, year = {2018}, volume = {113}, editor = {Parida, Laxmi and Ukkonen, Esko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.23}, URN = {urn:nbn:de:0030-drops-93256}, doi = {10.4230/LIPIcs.WABI.2018.23}, annote = {Keywords: Fragmentation trees, Computational mass spectrometry} }
Feedback for Dagstuhl Publishing