Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)
Pascal Baumann, Khushraj Madnani, Filip Mazowiecki, and Georg Zetzsche. Monus Semantics in Vector Addition Systems with States. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 10:1-10:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{baumann_et_al:LIPIcs.CONCUR.2023.10, author = {Baumann, Pascal and Madnani, Khushraj and Mazowiecki, Filip and Zetzsche, Georg}, title = {{Monus Semantics in Vector Addition Systems with States}}, booktitle = {34th International Conference on Concurrency Theory (CONCUR 2023)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-299-0}, ISSN = {1868-8969}, year = {2023}, volume = {279}, editor = {P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.10}, URN = {urn:nbn:de:0030-drops-190047}, doi = {10.4230/LIPIcs.CONCUR.2023.10}, annote = {Keywords: Vector addition systems, Overapproximation, Reachability, Coverability} }
Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)
Ashwani Anand and Georg Zetzsche. Priority Downward Closures. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 39:1-39:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{anand_et_al:LIPIcs.CONCUR.2023.39, author = {Anand, Ashwani and Zetzsche, Georg}, title = {{Priority Downward Closures}}, booktitle = {34th International Conference on Concurrency Theory (CONCUR 2023)}, pages = {39:1--39:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-299-0}, ISSN = {1868-8969}, year = {2023}, volume = {279}, editor = {P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.39}, URN = {urn:nbn:de:0030-drops-190339}, doi = {10.4230/LIPIcs.CONCUR.2023.39}, annote = {Keywords: downward closure, priority order, pushdown automata, non-deterministic finite automata, abstraction, computability} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche. Context-Bounded Analysis of Concurrent Programs (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{baumann_et_al:LIPIcs.ICALP.2023.3, author = {Baumann, Pascal and Ganardi, Moses and Majumdar, Rupak and Thinniyam, Ramanathan S. and Zetzsche, Georg}, title = {{Context-Bounded Analysis of Concurrent Programs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {3:1--3: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.3}, URN = {urn:nbn:de:0030-drops-180559}, doi = {10.4230/LIPIcs.ICALP.2023.3}, annote = {Keywords: Context-bounded analysis, Multi-threaded programs, Decidability} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche. Checking Refinement of Asynchronous Programs Against Context-Free Specifications. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 110:1-110:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{baumann_et_al:LIPIcs.ICALP.2023.110, author = {Baumann, Pascal and Ganardi, Moses and Majumdar, Rupak and Thinniyam, Ramanathan S. and Zetzsche, Georg}, title = {{Checking Refinement of Asynchronous Programs Against Context-Free Specifications}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {110:1--110:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.110}, URN = {urn:nbn:de:0030-drops-181622}, doi = {10.4230/LIPIcs.ICALP.2023.110}, annote = {Keywords: Asynchronous programs, VASS, Dyck languages, Language inclusion, Refinement verification} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Pascal Baumann, Roland Meyer, and Georg Zetzsche. Regular Separability in Büchi VASS. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 9:1-9:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{baumann_et_al:LIPIcs.STACS.2023.9, author = {Baumann, Pascal and Meyer, Roland and Zetzsche, Georg}, title = {{Regular Separability in B\"{u}chi VASS}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {9:1--9:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.9}, URN = {urn:nbn:de:0030-drops-176617}, doi = {10.4230/LIPIcs.STACS.2023.9}, annote = {Keywords: Separability problem, Vector addition systems, Infinite words, Decidability} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Markus Lohrey, Andreas Rosowski, and Georg Zetzsche. Membership Problems in Finite Groups. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 71:1-71:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2022.71, author = {Lohrey, Markus and Rosowski, Andreas and Zetzsche, Georg}, title = {{Membership Problems in Finite Groups}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {71:1--71:16}, 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.71}, URN = {urn:nbn:de:0030-drops-168694}, doi = {10.4230/LIPIcs.MFCS.2022.71}, annote = {Keywords: algorithms for finite groups, intersection non-emptiness problems, knapsack problems in groups} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Moses Ganardi, Rupak Majumdar, Andreas Pavlogiannis, Lia Schütze, and Georg Zetzsche. Reachability in Bidirected Pushdown VASS. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 124:1-124:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ganardi_et_al:LIPIcs.ICALP.2022.124, author = {Ganardi, Moses and Majumdar, Rupak and Pavlogiannis, Andreas and Sch\"{u}tze, Lia and Zetzsche, Georg}, title = {{Reachability in Bidirected Pushdown VASS}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {124:1--124:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.124}, URN = {urn:nbn:de:0030-drops-164651}, doi = {10.4230/LIPIcs.ICALP.2022.124}, annote = {Keywords: Vector addition systems, Pushdown, Reachability, Decidability, Complexity} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Pascal Baumann, Moses Ganardi, Ramanathan S. Thinniyam, and Georg Zetzsche. Existential Definability over the Subword Ordering. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 7:1-7:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{baumann_et_al:LIPIcs.STACS.2022.7, author = {Baumann, Pascal and Ganardi, Moses and Thinniyam, Ramanathan S. and Zetzsche, Georg}, title = {{Existential Definability over the Subword Ordering}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.7}, URN = {urn:nbn:de:0030-drops-158178}, doi = {10.4230/LIPIcs.STACS.2022.7}, annote = {Keywords: subword, subsequence, definability, expressiveness, first order logic, existential fragment, quantifier alternation} }
Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)
Aneesh K. Shetty, S. Krishna, and Georg Zetzsche. Scope-Bounded Reachability in Valence Systems. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 29:1-29:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{shetty_et_al:LIPIcs.CONCUR.2021.29, author = {Shetty, Aneesh K. and Krishna, S. and Zetzsche, Georg}, title = {{Scope-Bounded Reachability in Valence Systems}}, booktitle = {32nd International Conference on Concurrency Theory (CONCUR 2021)}, pages = {29:1--29:19}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.29}, URN = {urn:nbn:de:0030-drops-144069}, doi = {10.4230/LIPIcs.CONCUR.2021.29}, annote = {Keywords: multi-pushdown systems, underapproximations, valence systems, reachability} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Pascal Bergsträßer, Moses Ganardi, and Georg Zetzsche. A Characterization of Wreath Products Where Knapsack Is Decidable. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 11:1-11:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bergstraer_et_al:LIPIcs.STACS.2021.11, author = {Bergstr\"{a}{\ss}er, Pascal and Ganardi, Moses and Zetzsche, Georg}, title = {{A Characterization of Wreath Products Where Knapsack Is Decidable}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {11:1--11:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.11}, URN = {urn:nbn:de:0030-drops-136566}, doi = {10.4230/LIPIcs.STACS.2021.11}, annote = {Keywords: knapsack, wreath products, decision problems in group theory, decidability, discrete Heisenberg group, Baumslag-Solitar groups} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Markus Lohrey and Georg Zetzsche. Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 67:1-67:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2020.67, author = {Lohrey, Markus and Zetzsche, Georg}, title = {{Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {67:1--67:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.67}, URN = {urn:nbn:de:0030-drops-127364}, doi = {10.4230/LIPIcs.MFCS.2020.67}, annote = {Keywords: computational group theory, matrix problems, Baumslag-Solitar groups} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Pascal Baumann, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche. The Complexity of Bounded Context Switching with Dynamic Thread Creation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 111:1-111:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{baumann_et_al:LIPIcs.ICALP.2020.111, author = {Baumann, Pascal and Majumdar, Rupak and Thinniyam, Ramanathan S. and Zetzsche, Georg}, title = {{The Complexity of Bounded Context Switching with Dynamic Thread Creation}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {111:1--111:16}, 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.111}, URN = {urn:nbn:de:0030-drops-125187}, doi = {10.4230/LIPIcs.ICALP.2020.111}, annote = {Keywords: Dynamic thread creation, Bounded context switching, Asynchronous Programs, Safety verification, State reachability, Petri nets, Complexity, Succinctness, Counter Programs} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Michaël Cadilhac, Dmitry Chistikov, and Georg Zetzsche. Rational Subsets of Baumslag-Solitar Groups. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 116:1-116:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{cadilhac_et_al:LIPIcs.ICALP.2020.116, author = {Cadilhac, Micha\"{e}l and Chistikov, Dmitry and Zetzsche, Georg}, title = {{Rational Subsets of Baumslag-Solitar Groups}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {116:1--116:16}, 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.116}, URN = {urn:nbn:de:0030-drops-125238}, doi = {10.4230/LIPIcs.ICALP.2020.116}, annote = {Keywords: Rational subsets, Baumslag-Solitar groups, decidability, regular languages, pointed expansion} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Michael Figelius, Moses Ganardi, Markus Lohrey, and Georg Zetzsche. The Complexity of Knapsack Problems in Wreath Products. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 126:1-126:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{figelius_et_al:LIPIcs.ICALP.2020.126, author = {Figelius, Michael and Ganardi, Moses and Lohrey, Markus and Zetzsche, Georg}, title = {{The Complexity of Knapsack Problems in Wreath Products}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {126:1--126: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.126}, URN = {urn:nbn:de:0030-drops-125339}, doi = {10.4230/LIPIcs.ICALP.2020.126}, annote = {Keywords: algorithmic group theory, knapsack, wreath product} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Ramanathan S. Thinniyam and Georg Zetzsche. Regular Separability and Intersection Emptiness Are Independent Problems. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 51:1-51:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{thinniyam_et_al:LIPIcs.FSTTCS.2019.51, author = {Thinniyam, Ramanathan S. and Zetzsche, Georg}, title = {{Regular Separability and Intersection Emptiness Are Independent Problems}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {51:1--51:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.51}, URN = {urn:nbn:de:0030-drops-116138}, doi = {10.4230/LIPIcs.FSTTCS.2019.51}, annote = {Keywords: Regular separability, intersection emptiness, decidability} }
Feedback for Dagstuhl Publishing