15 citations · 79 across the 16 of their papers we have counts for
20 papers
The smallest grammar problem revisited
Hideo Bannai, Momoko Hirayama, Danny Hucke +4
In a seminal paper of Charikar et al. on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors,…
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…
Approximation ratio of RePair
Danny Hucke, Artur Jez, Markus Lohrey
In a seminal paper of Charikar et al.~on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors.…
Word equations in linear space
Artur Jeż
Satisfiability of word equations is an important problem in the intersection of formal languages and algebra: Given two sequences consisting of letters and variables we are to deci…
Solutions of Word Equations over Partially Commutative Structures
Volker Diekert, Artur Jeż, Manfred Kufleitner +1
Let be a free partially commutative monoid with involution and its quotient group (for example, a right-angled Artin or Coxeter group). We show that for any syste…
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…