Prague Stringology Conference 2026
Hiroto Fujimaru and Shunsuke Inenaga
On the Additive Sensitivity of CDAWG-grammars
| Abstract: |
| 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 exhibit an infinite family of strings for which the CDAWG-grammar size increases by 3g-21 after one edit, and we show that the worst-case additive sensitivity is upper bounded by 8g+4. |
| Download paper: |  |
 |
|
| BibTeX reference |