Abstract
Data compression is a significant problem in Computer Science, both in theory and practice.Grammar-based compression is of particular interest in data compression because it achieves good compression rates while enabling additional operations on the compressed string, such as substring extraction and indexing. The problem of finding the smallest grammar that generates a given string is NP…