On the sensitivity of CDAWG-grammars
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917543518666752 |
|---|---|
| author | Fujimaru, Hiroto Inenaga, Shunsuke |
| author_facet | Fujimaru, Hiroto Inenaga, Shunsuke |
| contents | 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 $8 g + 4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02415 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the sensitivity of CDAWG-grammars Fujimaru, Hiroto Inenaga, Shunsuke Data Structures and Algorithms 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 $8 g + 4$. |
| title | On the sensitivity of CDAWG-grammars |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.02415 |