Compressed range minimum queries
type: Item
instance of: scholarly article
title: Compressed range minimum queries
zbMATH Open document ID: 1435.68069
zbMATH Open document ID: 1517.68093
DOI: 10.1007/978-3-030-00479-8_17
DOI: 10.1016/J.TCS.2019.07.002
author: Seungbum Jo
author: Shay Mozes
author: Oren Weimann
author: Paweł Gawrychowski
published in: Theoretical Computer Science
published in: String Processing and Information Retrieval
publication date: 2020-02-20T00:00:00Z
publication date: 2023-07-28T00:00:00Z
full work available at URL: https://arxiv.org/abs/1902.04427
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68W32
zbMATH DE Number: 7170197
zbMATH DE Number: 7720101
zbMATH Keywords: RMQ
zbMATH Keywords: grammar compression
zbMATH Keywords: SLP
zbMATH Keywords: tree compression
zbMATH Keywords: Cartesian tree
MaRDI profile type: Publication
OpenAlex ID: W2954607443
arXiv ID: 1902.04427
cites work: Practical compressed suffix trees
cites work: Maintaining information in fully dynamic trees with top trees
cites work: LRM-trees: compressed indices, adaptive sorting, and compressed permutations
cites work: Tree compression with top trees
cites work: Random Access to Grammar-Compressed Strings and Trees
cites work: The Smallest Grammar Problem
cites work: On succinct representations of binary trees
cites work: On Cartesian trees and range minimum queries
cites work: Variations on the Common Subexpression Problem
cites work: Slowing Down Top Trees for Better Worst-Case Compression
cites work: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
cites work: Tree compression using string grammars
cites work: Balancing Straight-line Programs
cites work: Fast \(q\)-gram mining on SLP compressed strings
cites work: Approximation of smallest linear tree grammar
cites work: Grammar-Based Tree Compression
cites work: Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
cites work: A Space-Optimal Grammar Compression.
cites work: A unifying look at data structures
Wikidata QID: Q127552079
description: scientific article