Moses Ganardi
ganardi (at) mpisws (dot) org
I am a research group leader at the Max Planck Institute for Software Systems (MPISWS)
in Kaiserslautern, Germany.
In addition, I hold an Interim Professorship for Theoretical Computer Science at Leipzig University.
From May 2020 to Dec 2022, I was a postdoctoral researcher at MPISWS
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 infinitestate systems,
algorithms on compressed data, as well as algorithmic group theory.
News
Publications
Conference papers

Ramsey Quantifiers in Linear Arithmetics
Accepted for POPL 2024

ContextBounded Analysis of Concurrent Programs (Invited Talk)
Proceedings of ICALP 2023

Checking Refinement of Asynchronous Programs against ContextFree Specifications
Proceedings of ICALP 2023

Revisiting Membership Problems in Subclasses of Rational Relations
Proceedings of LICS 2023

Unboundedness problems for machines with reversalbounded counters
Proceedings of FoSSaCS 2023

ContextBounded Verification of ContextFree Specifications
Proceedings of POPL 2023

LowLatency Sliding Window Algorithms for Formal Languages
Proceedings of FSTTCS 2022

The complexity of bidirected reachability in valence systems
Proceedings of LICS 2022

Ramsey Quantifiers over Automatic Structures: Complexity and Applications to Verification
Proceedings of LICS 2022

Reachability in Bidirected Pushdown VASS
Proceedings of ICALP 2022

Existential Definability over the Subword Ordering
Proceedings of STACS 2022

Pattern Matching on GrammarCompressed Strings in Linear Time
Proceedings of SODA 2022

Compression by Contracting StraightLine Programs
Proceedings of ESA 2021

A Characterization of Wreath Products Where Knapsack Is Decidable
Proceedings of STACS 2021

The complexity of knapsack problems in wreath products
Proceedings of ICALP 2020

Automatic equivalence structures of polynomial growth
Proceedings of CSL 2020

Sliding window property testing for regular languages
Proceedings of ISAAC 2019

Balancing straightline programs
Proceedings of FOCS 2019

Derandomization of sliding window algorithms with strict correctness
Proceedings of CSR 2019

Visibly pushdown languages over sliding windows
Proceedings of STACS 2019

Sliding windows over contextfree languages
Proceedings of MFCS 2018

Randomized sliding window algorithms for regular languages
Proceedings of ICALP 2018

Knapsack problems for wreath products
Proceedings of STACS 2018

Automata theory on sliding windows
Proceedings of STACS 2018

Circuit Evaluation for Finite Semirings
Proceedings of STACS 2017

Querying regular languages over slidingwindows
Proceedings of FSTTCS 2016

On the Parallel Complexity of Bisimulation on Finite Systems
Proceedings of CSL 2016

Tree Compression Using String Grammars
Proceedings of LATIN 2016

Parity Games of Bounded TreeWidth and CliqueWidth
Proceedings of FoSSaCS 2015
Journal papers

Existential definability over the subword ordering
Logical Methods in Computer Science 19(4), 2023

Balancing StraightLine Programs
Journal of the ACM 68(4), 2021

Derandomization for Sliding Window Algorithms with Strict Correctness
Theory of Computing Systems 65, pp. 118, 2021

Universal tree source coding using grammarbased compression
IEEE Transactions on Information Theory 65(10), pp. 63996413, 2019

The complexity of bisimulation and simulation on finite systems
Logical Methods in Computer Science 14(4), 2018
Special Issue for CSL 2016

A universal tree balancing theorem
ACM Transactions on Computation Theory 11(1), Article No. 1, 2019

Circuits and expressions over finite semirings
ACM Transactions on Computation Theory 10(4), Article No. 15, 2018

Tree compression using string grammars
Algorithmica 80(3), pp. 885–917, 2018
Special Issue for LATIN 2016

Constructing small tree grammars and small circuits for formulas
Journal of Computer and System Sciences 86, pp. 136–158, 2017
Other

Language recognition in the sliding window model
PhD Thesis, Universität Siegen, 2019
Service
I am/have been on the PC of LICS 2024,
ESA 2023,
RP 2022,
CSR 2022resigned on March 3, 2022 due to sanctions against Russia..
I have reviewed submissions for
STACS 2024,
LATIN 2024,
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
PaulEhrlichStrasse, Building G 26
67663 Kaiserslautern, Germany