Imagen de Portada

On the sensitivity of CDAWG-grammars

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Fujimaru, Hiroto, Inenaga, Shunsuke
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Constant sensitivity on the CDAWGs
por: Hamai, Rikuya, et al.
Publicado: (2025)

Tight bounds for the sensitivity of CDAWGs with left-end edits
por: Fujimaru, Hiroto, et al.
Publicado: (2023)

On the number of MUSs crossing a position
por: Fujimaru, Hiroto, et al.
Publicado: (2025)

The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
por: Cleary, Alan M., et al.
Publicado: (2024)

Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
por: Inenaga, Shunsuke, et al.
Publicado: (2024)

Faster and Simpler Online Computation of String Net Frequency
por: Inenaga, Shunsuke
Publicado: (2024)

Relating Left and Right Extensions of Maximal Repeats
por: Inenaga, Shunsuke, et al.
Publicado: (2024)

All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings
por: Kikuchi, Masaru, et al.
Publicado: (2024)

Simple Linear-time Repetition Factorization
por: Yonemoto, Yuki, et al.
Publicado: (2024)

Space-Efficient Online Computation of String Net Occurrences
por: Mieno, Takuya, et al.
Publicado: (2024)

Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved
por: Inenaga, Shunsuke
Publicado: (2024)

Faster and simpler online/sliding rightmost Lempel-Ziv factorizations
por: Sumiyoshi, Wataru, et al.
Publicado: (2024)

Packed Acyclic Deterministic Finite Automata
por: Shibata, Hiroki, et al.
Publicado: (2024)

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
por: Shibata, Hiroki, et al.
Publicado: (2025)

Constant-time edge label and leaf pointer maintenance on sliding suffix trees
por: Leonard, Laurentius, et al.
Publicado: (2023)

Faster Space-Efficient STR-IC-LCS Computation
por: Yonemoto, Yuki, et al.
Publicado: (2022)

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
por: Cleary, Alan M., et al.
Publicado: (2024)

Edit and Alphabet-Ordering Sensitivity of Lex-parse
por: Nakashima, Yuto, et al.
Publicado: (2024)

Subsequence Matching and LCS with Segment Number Constraints
por: Yonemoto, Yuki, et al.
Publicado: (2024)

Counting distinct (non-)crossing substrings
por: Umezaki, Haruki, et al.
Publicado: (2025)

Computing maximal palindromes in non-standard matching models
por: Mieno, Takuya, et al.
Publicado: (2022)

Subsequence Matching and LCS under Cartesian-Tree Equivalence
por: Tsujimoto, Taketo, et al.
Publicado: (2024)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
por: Fujie, Yuto, et al.
Publicado: (2025)

Smallest Suffixient Sets: Effectiveness, Resilience, and Calculation
por: Fujimaru, Hiroto, et al.
Publicado: (2025)

Sensitivity of Repetitiveness Measures to String Reversal
por: Bannai, Hideo, et al.
Publicado: (2026)

Nyldon Factorization of Thue-Morse Words and Fibonacci Words
por: Kishi, Kaisei, et al.
Publicado: (2025)

On the Number of Non-equivalent Parameterized Squares in a String
por: Hamai, Rikuya, et al.
Publicado: (2024)

Online Computation of Palindromes and Suffix Trees on Tries
por: Shibata, Hiroki, et al.
Publicado: (2026)

Bit catastrophes for the Burrows-Wheeler Transform
por: Giuliani, Sara, et al.
Publicado: (2024)

Fast and memory-efficient BWT construction of repetitive texts using Lyndon grammars
por: Olbrich, Jannik
Publicado: (2025)

Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing
por: Diaz-Dominguez, Diego
Publicado: (2024)

Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
por: Giuliani, Sara, et al.
Publicado: (2020)

Average sensitivity of the Knapsack Problem
por: Kumabe, Soh, et al.
Publicado: (2024)

Engineering faster double-array Aho-Corasick automata
por: Kanda, Shunsuke, et al.
Publicado: (2022)

Incongruity-sensitive access to highly compressed strings
por: Cicalese, Ferdinando, et al.
Publicado: (2026)

NP-Completeness for the Space-Optimality of Double-Array Tries
por: Bannai, Hideo, et al.
Publicado: (2024)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
por: Censor-Hillel, Keren, et al.
Publicado: (2025)

Accelerating Probabilistic Response-Time Analysis: Revised Critical Instant and Optimized Convolution
por: Takahashi, Hiroto, et al.
Publicado: (2025)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
por: Munteanu, Alexander, et al.
Publicado: (2024)

Accelerating ERM for data-driven algorithm design using output-sensitive techniques
por: Balcan, Maria-Florina, et al.
Publicado: (2022)