2 citations · 9 across the 12 of their papers we have counts for
5 papers · 1 filter
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…
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…
Constructing small tree grammars and small circuits for formulas
Moses Ganardi, Danny Hucke, Artur Jez +2
It is shown that every tree of size over a fixed set of different ranked symbols can be decomposed (in linear time as well as in logspace) into $O\big(\frac{n}{\log_σn}\big…