Cover Image

Word Break on SLP-Compressed Texts

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	De, Rajat, Kempa, Dominik
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
by: Adudodla, Ankith Reddy, et al.
Published: (2025)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
by: De, Rajat, et al.
Published: (2025)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
by: De, Rajat, et al.
Published: (2023)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
by: Kempa, Dominik, et al.
Published: (2023)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
by: Kempa, Dominik, et al.
Published: (2025)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

Engineering Select Support for Hybrid Bitvectors
by: Chiu, Eric, et al.
Published: (2025)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
by: Kempa, Dominik, et al.
Published: (2025)

Wavelet Forests Revisited
by: Chiu, Eric, et al.
Published: (2026)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
by: Kempa, Dominik, et al.
Published: (2024)

LZ78 Substring Compression in Compressed Space
by: Shibata, Hiroki, et al.
Published: (2025)

Substring Compression Variations and LZ78-Derivates
by: Köppl, Dominik
Published: (2024)

Space-efficient SLP encoding for $O(\log N)$-time random access
by: Takasaka, Akito, et al.
Published: (2024)

Compressing Dynamic Fully Indexable Dictionaries in Word-RAM
by: Domingues, Gabriel Marques
Published: (2026)

Algorithms for Galois Words: Detection, Factorization, and Rotation
by: Hendrian, Diptarama, et al.
Published: (2024)

LZD-style Compression Scheme with Truncation and Repetitions
by: Götz, Linus, et al.
Published: (2025)

V-Words, Lyndon Words and Galois Words
by: Daykin, Jacqueline W., et al.
Published: (2024)

Revisiting the Sparse Matrix Compression Problem
by: Jugé, Vincent, et al.
Published: (2026)

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
by: Duyster, Anouk, et al.
Published: (2025)

Subsequence Covers of Words
by: Charalampopoulos, Panagiotis, et al.
Published: (2025)

Revisiting Token Sliding on Chordal Graphs
by: Adak, Rajat, et al.
Published: (2025)

Exploring Word-Representable Temporal Graphs
by: Adamson, Duncan
Published: (2025)

Compressed Index with Construction in Compressed Space
by: Kosolobov, Dmitry
Published: (2026)

Breaking the Bellman-Ford Shortest-Path Bound
by: Elmasry, Amr
Published: (2024)

Dynamic Range Minimum Queries on the Ultra-Wide Word RAM
by: Bille, Philip, et al.
Published: (2024)

Compressed Game Solving
by: Considine, Jeffrey
Published: (2024)

Bubble-Flip -- A New Generation Algorithm for Prefix Normal Words
by: Cicalese, Ferdinando, et al.
Published: (2017)

Near-real-time Solutions for Online String Problems
by: Köppl, Dominik, et al.
Published: (2026)

Smallest suffixient set maintenance in near-real-time
by: Köppl, Dominik, et al.
Published: (2026)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

Sketching and Streaming for Dictionary Compression
by: Becker, Ruben, et al.
Published: (2023)

String Indexing with Compressed Patterns
by: Bille, Philip, et al.
Published: (2019)

A Gentle Wakeup Call: Symmetry Breaking with Less Collision Cost
by: Biswas, Umesh, et al.
Published: (2025)

ExpoSort: Breaking the quasi-polynomial-time barrier for reluctant sorting
by: Abrahamsen, Mikkel
Published: (2024)

Bin Packing under Random-Order: Breaking the Barrier of 3/2
by: Hebbar, Anish, et al.
Published: (2024)

Extending the Burrows-Wheeler Transform for Cartesian Tree Matching and Constructing It
by: Osterkamp, Eric M., et al.
Published: (2024)

Compressing Hypergraphs using Suffix Sorting
by: Adler, Enno, et al.
Published: (2025)

Compressing Suffix Trees by Path Decompositions
by: Becker, Ruben, et al.
Published: (2025)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
by: Chuzhoy, Julia, et al.
Published: (2025)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2025)