Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences

DOI10.1137/S0097539790189733MaRDI QIDQ4286226zbMATH OpenOpenAlexFDO

Authors Rajamani Sundar, Robert E. Tarjan

Publication date 27 March 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539790189733

zbMATH Keywords

\(S\)-expressionsabstract data typebinary search treesdata structuresdictionaryequality testingprogramming languagesunique representation

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• Representing sets with constant time equality testing
• Compact representations of ordered sets
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• An improved scheme for set equality testing and updating
• scientific article; zbMATH DE number 2038723

Cited in

(14)

• An improved scheme for set equality testing and updating
• EXPtime tableaux for ALC
• Dynamic and internal longest common substring
• Representing sets with constant time equality testing
• Equality testing for complex objects based on hashing
• scientific article; zbMATH DE number 1003252 (Why is no real title available?)
• Longest common substring made fully dynamic
• Representation transformations of ordered lists
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• A textbook solution for dynamic strings
• Minimizing tardy processing time on a single machine in near-linear time
• Minimizing tardy processing time on a single machine in near-linear time
• A textbook solution for dynamic strings
• B-treaps revised: write efficient randomized block search trees with high load

This page was built for publication: Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences

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