Cover Image

Algorithms for Galois Words: Detection, Factorization, and Rotation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hendrian, Diptarama, Köppl, Dominik, Yoshinaka, Ryo, Shinohara, Ayumi
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Height-bounded Lempel-Ziv encodings
by: Bannai, Hideo, et al.
Published: (2024)

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

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

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

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

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

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

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

Bijective BWT based compression schemes
by: Badkobeh, Golnaz, et al.
Published: (2024)

Hardness Results on Characteristics for Elastic-Degenerated Strings
by: Köppl, Dominik, et al.
Published: (2024)

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

Space-time Trade-offs for the LCP Array of Wheeler DFAs
by: Cotumaccio, Nicola, et al.
Published: (2023)

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

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

Word Break on SLP-Compressed Texts
by: De, Rajat, et al.
Published: (2025)

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

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

Finding Order-Preserving Subgraphs
by: Imamura, Haruya, et al.
Published: (2025)

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

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

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

Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2023)

An O(1) Space Algorithm for N-Dimensional Tensor Rotation: A Generalization of the Reversal Method
by: Chen, Dexin
Published: (2025)

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

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
by: Zhou, Jianqi, et al.
Published: (2025)

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

Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model
by: Suzuki, Ryo, et al.
Published: (2026)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
by: Cohen-Addad, Vincent, et al.
Published: (2025)

On Rotation Distance of Rank Bounded Trees
by: M., Anoop S. K., et al.
Published: (2023)

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

Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
by: Mieno, Takuya, et al.
Published: (2024)

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

A Polynomial-time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs
by: Cenciarelli, Pietro, et al.
Published: (2016)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, 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)

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

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

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

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