A simple optimal representation for balanced parentheses

DOI10.1016/j.tcs.2006.09.014zbMath1103.68040MaRDI QIDQ859854

Rajeev Raman, Naila Rahman, Venkatesh Raman, Richard F. Geary

Publication date: 22 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.09.014

zbMATH Keywords

succinct data structures; compressed dictionaries; parentheses representation of trees; XML DOM

Mathematics Subject Classification ID

68P05: Data structures

Related Items

ENCRYPTION OF 3D PLANE IN GIS USING VORONOI-DELAUNAY TRIANGULATIONS AND CATALAN NUMBERS, Fast matching statistics in small space, Space-Efficient Euler Partition and Bipartite Edge Coloring, Fast and compact planar embeddings, Random generation and enumeration of bipartite permutation graphs, Ultra-succinct representation of ordered trees with applications, Succinct representations of permutations and functions, Simple and efficient fully-functional succinct trees, Space-efficient construction of Lempel-Ziv compressed text indexes, Encoding 2D range maximum queries, Faster entropy-bounded compressed suffix trees, Space-efficient Euler partition and bipartite edge coloring, Practical compressed suffix trees, Linked dynamic tries with applications to LZ-compression in sublinear time and space, On succinct representations of binary trees, Improved range minimum queries, Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits, Succinct data structure for dynamic trees with faster queries, GLOUDS: representing tree-like graphs, Representation of ordered trees with a given degree distribution, Succinct encoding of binary strings representing triangulations, Fully Functional Static and Dynamic Succinct Trees, General Document Retrieval in Compact Space, Succinct Representations of Ordinal Trees, Encodings of Range Maximum-Sum Segment Queries and Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Representing trees of higher degree
• Space Efficient Suffix Trees
• Deterministic Dictionaries
• Succinct Representation of Balanced Parentheses and Static Trees
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• An experimental study of a compressed index