arXiv Open Access 2025

On the sensitivity of CDAWG-grammars

Hiroto Fujimaru Shunsuke Inenaga

Lihat Sumber

Abstrak

The compact directed acyclic word graphs (CDAWG) [Blumer et al. 1987] of a string is the minimal compact automaton that recognizes all the suffixes of the string. CDAWGs are known to be useful 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. In this paper, we prove that the CDAWG-grammar size $g$ can increase by at most an additive factor of $4e + 4$ than the original after any single-character edit operation is performed on the input string, where $e$ denotes the number of edges in the corresponding CDAWG before the edit.

Topik & Kata Kunci

cs.DS

Penulis (2)

Hiroto Fujimaru

Shunsuke Inenaga

Format Sitasi

APA MLA BibTeX

Fujimaru, H., Inenaga, S. (2025). On the sensitivity of CDAWG-grammars. https://arxiv.org/abs/2503.02415

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓