On the sensitivity of CDAWG-grammars

The compact directed acyclic word graph (CDAWG) [Blumer et al. 1987] of a string is the minimal compact automaton that recognizes all the suffixes of the string. CDAWGs can be used for various string tasks including text pattern searching, data compression, and pattern discovery. The CDAWG-grammar [Belazzougui & Cunial 2017] is a grammar-based text compression based on the CDAWG, which allows for representing the CDAWG in $O(e)$ space without storing the string, where $e$ denotes the number of CDAWG edges. Let $g$ be the size of the CDAWG-grammar for the input string $T$. We show that the worst-case additive sensitivity of the CDAWG-grammar is lower bounded by $3g-21$ and is upper bounded by $8g+4$.