2 citations · 9 across the 12 of their papers we have counts for
28 papers
On the complexity of computing Strahler numbers
Moses Ganardi, Markus Lohrey
It is shown that the problem of computing the Strahler number of a binary tree given as a term is complete for the circuit complexity class uniform . For several var…
Fast Ramsey Quantifier Elimination in LIRA (with applications to liveness checking)
Kilian Lichtner, Pascal Bergsträßer, Moses Ganardi +2
Ramsey quantifiers have recently been proposed as a unified framework for handling properties of interests in program verification involving proofs in the form of infinite cliques,…
Regular Languages in the Sliding Window Model
Moses Ganardi, Danny Hucke, Markus Lohrey +2
We study the space complexity of the following problem: For a fixed regular language , we receive a stream of symbols and want to test membership of a sliding window of size …
Directed Regular and Context-Free Languages
Moses Ganardi, Irmak Saglam, Georg Zetzsche
We study the problem of deciding whether a given language is directed. A language is \emph{directed} if every pair of words in have a common (scattered) superword in . D…
Ramsey Quantifiers in Linear Arithmetics
Pascal Bergsträßer, Moses Ganardi, Anthony W. Lin +1
We study Satisfiability Modulo Theories (SMT) enriched with the so-called Ramsey quantifiers, which assert the existence of cliques (complete graphs) in the graph induced by some f…
Checking Refinement of Asynchronous Programs against Context-Free Specifications
Pascal Baumann, Moses Ganardi, Rupak Majumdar +2
In the language-theoretic approach to refinement verification, we check that the language of traces of an implementation all belong to the language of a specification. We consider…
Revisiting Membership Problems in Subclasses of Rational Relations
Pascal Bergsträßer, Moses Ganardi
We revisit the membership problem for subclasses of rational relations over finite and infinite words: Given a relation R in a class C_2, does R belong to a smaller class C_1? The…
Unboundedness problems for machines with reversal-bounded counters
Pascal Baumann, Flavio D'Alessandro, Moses Ganardi +4
We consider a general class of decision problems concerning formal languages, called ``(one-dimensional) unboundedness predicates'', for automata that feature reversal-bounded coun…
Existential Definability over the Subword Ordering
Pascal Baumann, Moses Ganardi, Ramanathan S. Thinniyam +1
We study first-order logic (FO) over the structure consisting of finite words over some alphabet , together with the (non-contiguous) subword ordering. In terms of decidability…
Low-Latency Sliding Window Algorithms for Formal Languages
Moses Ganardi, Louis Jachiet, Markus Lohrey +1
Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For…
Ramsey Quantifiers over Automatic Structures: Complexity and Applications to Verification
Pascal Bergsträßer, Moses Ganardi, Anthony W. Lin +1
Automatic structures are infinite structures that are finitely represented by synchronized finite-state automata. This paper concerns specifically automatic structures over finite…
Reachability in Bidirected Pushdown VASS
Moses Ganardi, Rupak Majumdar, Andreas Pavlogiannis +2
A pushdown vector addition system with states (PVASS) extends the model of vector addition systems with a pushdown store. A PVASS is said to be \emph{bidirected} if every transitio…
Pattern Matching on Grammar-Compressed Strings in Linear Time
Moses Ganardi, Paweł Gawrychowski
The most fundamental problem considered in algorithms for text processing is pattern matching: given a pattern of length and a text of length , does occur in …
The complexity of bidirected reachability in valence systems
Moses Ganardi, Rupak Majumdar, Georg Zetzsche
Reachability problems in infinite-state systems are often subject to extremely high complexity. This motivates the investigation of efficient overapproximations, where we add trans…
Compression by Contracting Straight-Line Programs
Moses Ganardi
In grammar-based compression a string is represented by a context-free grammar, also called a straight-line program (SLP), that generates only that string. We refine a recent balan…
A characterization of wreath products where knapsack is decidable
Pascal Bergsträßer, Moses Ganardi, Georg Zetzsche
The knapsack problem for groups was introduced by Miasnikov, Nikolaev, and Ushakov. It is defined for each finitely generated group and takes as input group elements $g_1,\ldot…
The complexity of knapsack problems in wreath products
Michael Figelius, Moses Ganardi, Markus Lohrey +1
We prove new complexity results for computational problems in certain wreath products of groups and (as an application) for free solvable group. For a finitely generated group we s…
Sliding window property testing for regular languages
Moses Ganardi, Danny Hucke, Markus Lohrey +1
We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the…
Balancing Straight-Line Programs
Moses Ganardi, Artur Jeż, Markus Lohrey
It is shown that a context-free grammar of size that produces a single string (such a grammar is also called a string straight-line program) can be transformed in linear ti…
Visibly Pushdown Languages over Sliding Windows
Moses Ganardi
We investigate the class of visibly pushdown languages in the sliding window model. A sliding window algorithm for a language receives a stream of symbols and has to decide at…
The Complexity of Bisimulation and Simulation on Finite Systems
Moses Ganardi, Stefan Göller, Markus Lohrey
In this paper the computational complexity of the (bi)simulation problem over restricted graph classes is studied. For trees given as pointer structures or terms the (bi)simulation…
Randomized sliding window algorithms for regular languages
Moses Ganardi, Danny Hucke, Markus Lohrey
A sliding window algorithm receives a stream of symbols and has to output at each time instant a certain value which only depends on the last symbols. If the algorithm is rando…
Knapsack Problems for Wreath Products
Moses Ganardi, Daniel König, Markus Lohrey +1
In recent years, knapsack problems for (in general non-commutative) groups have attracted attention. In this paper, the knapsack problem for wreath products is studied. It turns ou…
A universal tree balancing theorem
Moses Ganardi, Markus Lohrey
We present a general framework for balancing expressions (terms) in form of so called tree straight-line programs. The latter can be seen as circuits over the free term algebra ext…