Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Moses Ganardi, Irmak Sağlam, and Georg Zetzsche. Directed Regular and Context-Free Languages. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ganardi_et_al:LIPIcs.STACS.2024.36, author = {Ganardi, Moses and Sa\u{g}lam, Irmak and Zetzsche, Georg}, title = {{Directed Regular and Context-Free Languages}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {36:1--36:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.36}, URN = {urn:nbn:de:0030-drops-197465}, doi = {10.4230/LIPIcs.STACS.2024.36}, annote = {Keywords: Subword, ideal, language, regular, context-free, equivalence, downward closure, compression} }
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-dev.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-dev.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 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Moses Ganardi, Louis Jachiet, Markus Lohrey, and Thomas Schwentick. Low-Latency Sliding Window Algorithms for Formal Languages. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 38:1-38:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ganardi_et_al:LIPIcs.FSTTCS.2022.38, author = {Ganardi, Moses and Jachiet, Louis and Lohrey, Markus and Schwentick, Thomas}, title = {{Low-Latency Sliding Window Algorithms for Formal Languages}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {38:1--38:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.38}, URN = {urn:nbn:de:0030-drops-174301}, doi = {10.4230/LIPIcs.FSTTCS.2022.38}, annote = {Keywords: Streaming algorithms, regular languages, context-free languages} }
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-dev.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-dev.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 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Moses Ganardi. Compression by Contracting Straight-Line Programs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ganardi:LIPIcs.ESA.2021.45, author = {Ganardi, Moses}, title = {{Compression by Contracting Straight-Line Programs}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {45:1--45:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.45}, URN = {urn:nbn:de:0030-drops-146263}, doi = {10.4230/LIPIcs.ESA.2021.45}, annote = {Keywords: grammar-based compression, balancing, finger search} }
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-dev.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 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Armin Weiß. Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 102:1-102:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{wei:LIPIcs.ICALP.2020.102, author = {Wei{\ss}, Armin}, title = {{Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {102:1--102: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.102}, URN = {urn:nbn:de:0030-drops-125093}, doi = {10.4230/LIPIcs.ICALP.2020.102}, annote = {Keywords: equations in groups, solvable groups, exponential time hypothesis} }
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-dev.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 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Moses Ganardi and Bakhadyr Khoussainov. Automatic Equivalence Structures of Polynomial Growth. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ganardi_et_al:LIPIcs.CSL.2020.21, author = {Ganardi, Moses and Khoussainov, Bakhadyr}, title = {{Automatic Equivalence Structures of Polynomial Growth}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {21:1--21:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-132-0}, ISSN = {1868-8969}, year = {2020}, volume = {152}, editor = {Fern\'{a}ndez, Maribel 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.CSL.2020.21}, URN = {urn:nbn:de:0030-drops-116645}, doi = {10.4230/LIPIcs.CSL.2020.21}, annote = {Keywords: automatic structures, polynomial growth, isomorphism problem} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding Window Property Testing for Regular Languages. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ganardi_et_al:LIPIcs.ISAAC.2019.6, author = {Ganardi, Moses and Hucke, Danny and Lohrey, Markus and Starikovskaya, Tatiana}, title = {{Sliding Window Property Testing for Regular Languages}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.6}, URN = {urn:nbn:de:0030-drops-115023}, doi = {10.4230/LIPIcs.ISAAC.2019.6}, annote = {Keywords: Streaming algorithms, approximation algorithms, regular languages} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Moses Ganardi. Visibly Pushdown Languages over Sliding Windows. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ganardi:LIPIcs.STACS.2019.29, author = {Ganardi, Moses}, title = {{Visibly Pushdown Languages over Sliding Windows}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {29:1--29:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.29}, URN = {urn:nbn:de:0030-drops-102688}, doi = {10.4230/LIPIcs.STACS.2019.29}, annote = {Keywords: visibly pushdown languages, sliding windows, rational transductions} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Moses Ganardi, Artur Jez, and Markus Lohrey. Sliding Windows over Context-Free Languages. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ganardi_et_al:LIPIcs.MFCS.2018.15, author = {Ganardi, Moses and Jez, Artur and Lohrey, Markus}, title = {{Sliding Windows over Context-Free Languages}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {15:1--15:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul 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.MFCS.2018.15}, URN = {urn:nbn:de:0030-drops-95973}, doi = {10.4230/LIPIcs.MFCS.2018.15}, annote = {Keywords: sliding windows, streaming algorithms, context-free languages} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Moses Ganardi, Danny Hucke, and Markus Lohrey. Randomized Sliding Window Algorithms for Regular Languages. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 127:1-127:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ganardi_et_al:LIPIcs.ICALP.2018.127, author = {Ganardi, Moses and Hucke, Danny and Lohrey, Markus}, title = {{Randomized Sliding Window Algorithms for Regular Languages}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {127:1--127:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.127}, URN = {urn:nbn:de:0030-drops-91317}, doi = {10.4230/LIPIcs.ICALP.2018.127}, annote = {Keywords: sliding windows, regular languages, randomized complexity} }
Feedback for Dagstuhl Publishing