Maintaining dynamic sequences under equality tests in polylogarithmic time

DOI10.1007/BF02522825zbMATH Open0865.68034OpenAlexW3138321435MaRDI QIDQ675314FDOQ675314

K. Mehlhorn, Rajamani Sundar, Christian Uhrig

Publication date: 30 June 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02522825

zbMATH Keywords

randomizationdata structurederandomization

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Dynamic Perfect Hashing: Upper and Lower Bounds
• Making data structures persistent
• Parallel Symmetry-Breaking in Sparse Graphs
• Deterministic coin tossing with applications to optimal parallel list ranking

Cited In (30)

• One-variable word equations in linear time
• Representing sets with constant time equality testing
• Text sparsification via local maxima.
• SLP compression for solutions of equations with constraints in free and hyperbolic groups
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Grammar-based compression of unranked trees
• An LMS-based grammar self-index with local consistency properties
• Grammar index by induced suffix sorting
• Inter-procedural Two-Variable Herbrand Equalities
• Compressed decision problems in hyperbolic groups
• Dynamic and internal longest common substring
• Faster Algorithms for All Pairs Non-Decreasing Paths Problem
• The complexity of compressed membership problems for finite automata
• Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences
• Internal pattern matching queries in a text and applications
• Languages and Compilers for Parallel Computing
• Parallel Identity Testing for Skew Circuits with Big Powers and Applications
• Near-optimal search time in \(\delta \)-optimal space
• Approximation of smallest linear tree grammar
• Parallel identity testing for skew circuits with big powers and applications
• A compressed dynamic self-index for highly repetitive text collections
• Approximation of grammar-based compression via recompression
• Fast and simple compact hashing via bucketing
• Repetition Detection in a Dynamic String
• Title not available (Why is that?)
• Cyclotomic identity testing and applications
• Space-efficient conversions from SLPs
• Dynamic index and LZ factorization in compressed space
• Near-optimal search time in \(\delta \)-optimal space, and vice versa
• Longest common substring made fully dynamic

   Recommendations

• Title not available (Why is that?) 👍 👎
• Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences 👍 👎
• An improved scheme for set equality testing and updating 👍 👎
• Representing sets with constant time equality testing 👍 👎

This page was built for publication: Maintaining dynamic sequences under equality tests in polylogarithmic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q675314)