A simple optimal representation for balanced parentheses

DOI10.1016/j.tcs.2006.09.014zbMath1103.68040OpenAlexW2161715626MaRDI 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 structurescompressed dictionariesparentheses representation of treesXML DOM

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (25)

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

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

This page was built for publication: A simple optimal representation for balanced parentheses