Balancing Straight-line Programs

We show that a context-free grammar of size that produces a single string of length (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for of size , whose unique derivation tree has depth . This solves an open problem in the a...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2021-08, Vol.68 (4), p.1-40
Main Authors: Ganardi, Moses, Jeż, Artur, Lohrey, Markus
Format: Article
Language:English
Subjects:
Balancing
Circuits
Context
Rings (mathematics)
Strings
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!