What type of study is this?

This is a Quantitative Study study.

October 20, 2025Open Access

On the sensitivity of CDAWG-grammars

Key Points

The size of CDAWG-grammar increases by at most an additive factor after edits.
An additive factor of $4e + 4$ is established in relation to edges in CDAWG.
CDAWGs are crucial for tasks like text pattern searching and data compression.
Single-character edits have defined constraints on grammar size growth.

Abstract

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.

Read Full Paperexternally

Ask AI

Helpful

Bookmark

View Full Paper

Cite This Study

Fujimaru et al. (Tue,) studied this question.

synapsesocial.com/papers/68f5fcce8d54a28a75cf19be https://doi.org/https://doi.org/10.48550/arxiv.2503.02415