8 papers
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 …
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…
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…