Moses Ganardi

ganardi (at) mpi-sws (dot) org

I am a research group leader at the Max Planck Institute for Software Systems (MPI-SWS) in Kaiserslautern, Germany. From May 2020 to Dec 2022, I was a postdoctoral researcher at MPI-SWS in the Models of Computation group headed by Georg Zetzsche. Before that, I obtained a PhD with Markus Lohrey at the University of Siegen.

My research interests include automata theory, logic in computer science, verification of infinite-state systems, algorithms on compressed data, as well as algorithmic group theory.

News

• Two papers accepted for LICS 2023 and ICALP 2023.
• I am on the PC of ESA 2023 (Track A).
• I am on the PC of RP 2022.
• Invited Speaker at the ICALP 2022 workshop Straight-Line Programs, Word Equations and their Interplay.
• Highlight Talk at CPM 2022.

Publications

Conference papers

• Checking Refinement of Asynchronous Programs against Context-Free Specifications
  with Pascal Baumann, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche
  Accepted for ICALP 2023
• Revisiting Membership Problems in Subclasses of Rational Relations
  with Pascal Bergsträßer
  Accepted for LICS 2023
  [arxiv]
• Unboundedness problems for machines with reversal-bounded counters
  with Pascal Baumann, Flavio D'Alessandro, Oscar H. Ibarra, Ian McQuillan, Lia Schütze, and Georg Zetzsche
  Proceedings of FoSSaCS 2023
  [doi] [arxiv]
• Context-Bounded Verification of Context-Free Specifications
  with Pascal Baumann, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche
  Proceedings of POPL 2023
  [doi]
• Low-Latency Sliding Window Algorithms for Formal Languages
  with Louis Jachiet, Markus Lohrey, and Thomas Schwentick
  Proceedings of FSTTCS 2022
  [doi] [arxiv]
• The complexity of bidirected reachability in valence systems
  with Rupak Majumdar and Georg Zetzsche
  Proceedings of LICS 2022
  [doi] [arxiv]
• Ramsey Quantifiers over Automatic Structures: Complexity and Applications to Verification
  with Pascal Bergsträßer, Anthony W. Lin, and Georg Zetzsche
  Proceedings of LICS 2022
  [doi] [arxiv]
• Reachability in Bidirected Pushdown VASS
  with Rupak Majumdar, Andreas Pavlogiannis, Lia Schütze, and Georg Zetzsche
  Proceedings of ICALP 2022
  [doi] [arxiv]
• Existential Definability over the Subword Ordering
  with Pascal Baumann, Ramanathan S. Thinniyam, and Georg Zetzsche
  Proceedings of STACS 2022
  [doi]
• Pattern Matching on Grammar-Compressed Strings in Linear Time
  with Paweł Gawrychowski
  Proceedings of SODA 2022
  [doi] [arxiv]
• Compression by Contracting Straight-Line Programs
  Proceedings of ESA 2021
  [doi] [arxiv]
• A Characterization of Wreath Products Where Knapsack Is Decidable
  with Pascal Bergsträßer and Georg Zetzsche
  Proceedings of STACS 2021
  [doi] [arxiv]
• The complexity of knapsack problems in wreath products
  with Michael Figelius, Markus Lohrey, and Georg Zetzsche
  Proceedings of ICALP 2020
  [doi] [arxiv]
• Automatic equivalence structures of polynomial growth
  with Bakhadyr Khoussainov
  Proceedings of CSL 2020
  [doi]
• Sliding window property testing for regular languages
  with Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya
  Proceedings of ISAAC 2019
  [doi] [arxiv]
• Balancing straight-line programs
  with Artur Jeż and Markus Lohrey
  Proceedings of FOCS 2019
  [doi] [arxiv]
• Derandomization of sliding window algorithms with strict correctness
  with Danny Hucke and Markus Lohrey
  Proceedings of CSR 2019
  [doi]
• Visibly pushdown languages over sliding windows
  Proceedings of STACS 2019
  [doi] [arxiv]
• Sliding windows over context-free languages
  with Artur Jeż and Markus Lohrey
  Proceedings of MFCS 2018
  [doi]
• Randomized sliding window algorithms for regular languages
  with Danny Hucke and Markus Lohrey
  Proceedings of ICALP 2018
  [doi] [arxiv]
• Knapsack problems for wreath products
  with Daniel König, Markus Lohrey, and Georg Zetzsche
  Proceedings of STACS 2018
  [doi] [arxiv]
• Automata theory on sliding windows
  with Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras
  Proceedings of STACS 2018
  [doi] [arxiv]
• Circuit Evaluation for Finite Semirings
  with Danny Hucke, Daniel König, and Markus Lohrey
  Proceedings of STACS 2017
  [doi]
• Querying regular languages over sliding-windows
  with Danny Hucke and Markus Lohrey
  Proceedings of FSTTCS 2016
  [doi]
• On the Parallel Complexity of Bisimulation on Finite Systems
  with Stefan Göller and Markus Lohrey
  Proceedings of CSL 2016
  [doi]
• Tree Compression Using String Grammars
  with Danny Hucke, Markus Lohrey, and Eric Noeth
  Proceedings of LATIN 2016
  [doi] [arxiv]
• Parity Games of Bounded Tree-Width and Clique-Width
  Proceedings of FoSSaCS 2015
  [doi]

Journal papers

• Balancing Straight-Line Programs
  with Artur Jeż and Markus Lohrey
  Journal of the ACM 68(4), 2021
  [doi] [arxiv]
• Derandomization for Sliding Window Algorithms with Strict Correctness
  with Danny Hucke and Markus Lohrey
  Theory of Computing Systems 65, pp. 1-18, 2021
  [doi]
• Universal tree source coding using grammar-based compression
  with Danny Hucke, Markus Lohrey, and Louisa Seelbach Benkner
  IEEE Transactions on Information Theory 65(10), pp. 6399-6413, 2019
  [doi]
• The complexity of bisimulation and simulation on finite systems
  with Stefan Göller and Markus Lohrey
  Logical Methods in Computer Science 14(4), 2018
  Special Issue for CSL 2016
  [doi]
• A universal tree balancing theorem
  with Markus Lohrey
  ACM Transactions on Computation Theory 11(1), Article No. 1, 2019
  [doi]
• Circuits and expressions over finite semirings
  with Danny Hucke, Daniel König, and Markus Lohrey
  ACM Transactions on Computation Theory 10(4), Article No. 15, 2018
  [doi]
• Tree compression using string grammars
  with Danny Hucke, Markus Lohrey, and Eric Noeth
  Algorithmica 80(3), pp. 885–917, 2018
  Special Issue for LATIN 2016
  [doi]
• Constructing small tree grammars and small circuits for formulas
  with Danny Hucke, Artur Jeż, Markus Lohrey, and Eric Noeth
  Journal of Computer and System Sciences 86, pp. 136–158, 2017
  [doi]

Other

• Language recognition in the sliding window model
  PhD Thesis, Universität Siegen, 2019
  [doi]

Service

I am/have been on the PC of ESA 2023, RP 2022, CSR 2022resigned on March 3, 2022 due to sanctions against Russia..

I have reviewed submissions for LICS 2023, ICALP 2023, STACS 2023, SODA 2023, CSL 2023, GandALF 2022, LATIN 2022, CPM 2022, CSL 2022, ICALP 2021, CiE 2021, LICS 2021, MFCS 2021, MFCS 2020, LATA 2020, ICALP 2019, DLT 2019, MFCS 2018, CIAA 2017, MFCS 2016, LMCS, Theory of Computing.

Contact

Moses Ganardi
Max Planck Institute for Software Systems
Paul-Ehrlich-Strasse, Building G 26
67663 Kaiserslautern, Germany