On the public citation graph

Maintaining dynamic sequences under equality tests in polylogarithmic time

https://doi.org/10.1007/bf02522825
0 signed · 96 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1016/0022-0000(89)90034-2openalex-snapshot
Making data structures persistent
inferredcites →https://doi.org/10.1016/s0019-9958(86)80023-7openalex-snapshot
Deterministic coin tossing with applications to optimal parallel list ranking
inferredcites →https://doi.org/10.1109/sfcs.1988.21968openalex-snapshot
Dynamic Perfect Hashing: Upper and Lower Bounds
inferredcites →https://doi.org/10.1137/0401044openalex-snapshot
Parallel Symmetry-Breaking in Sparse Graphs
inferredcites →https://doi.org/10.1145/100216.100219openalex-snapshot
Unique binary search tree representations and equality-testing of sets and sequences
inferredcites →https://doi.org/10.1145/75277.75305openalex-snapshot
Incremental computation via function caching

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/spe.2481openalex-snapshot
Sampled suffix array with minimizers
inferred← citeshttps://doi.org/10.1007/3-540-44450-5_23openalex-snapshot
Text Sparsification via Local Maxima
inferred← citeshttps://doi.org/10.1007/3-540-60220-8_54openalex-snapshot
Dynamic algorithms for the Dyck languages
inferred← citeshttps://doi.org/10.1007/978-1-4939-0748-9openalex-snapshot
The Compressed Word Problem for Groups
inferred← citeshttps://doi.org/10.1007/978-1-4939-0748-9_3openalex-snapshot
Algorithms on Compressed Words
inferred← citeshttps://doi.org/10.1007/978-3-030-40608-0_4openalex-snapshot
Recompression: Technique for Word Equations and Compressed Data
inferred← citeshttps://doi.org/10.1007/978-3-030-86692-1_8openalex-snapshot
Grammar Index by Induced Suffix Sorting
inferred← citeshttps://doi.org/10.1007/978-3-030-86692-1_9openalex-snapshot
An LMS-Based Grammar Self-index with Local Consistency Properties
inferred← citeshttps://doi.org/10.1007/978-3-031-20624-5_6openalex-snapshot
Near-Optimal Search Time in $$\delta $$-Optimal Space
inferred← citeshttps://doi.org/10.1007/978-3-031-55598-5_10openalex-snapshot
Space-Efficient Conversions from SLPs
inferred← citeshttps://doi.org/10.1007/978-3-319-23660-5_2openalex-snapshot
Equality Testing of Compressed Strings
inferred← citeshttps://doi.org/10.1007/978-3-319-23826-5_28openalex-snapshot
Sampling the Suffix Array with Minimizers
inferred← citeshttps://doi.org/10.1007/978-3-319-46049-9_24openalex-snapshot
Longest Common Abelian Factors and Large Alphabets
inferred← citeshttps://doi.org/10.1007/978-3-319-77404-6_25openalex-snapshot
Compressed Indexing with Signature Grammars
inferred← citeshttps://doi.org/10.1007/978-3-319-90530-3_11openalex-snapshot
Grammar-Based Compression of Unranked Trees
inferred← citeshttps://doi.org/10.1007/978-3-642-31594-7_45openalex-snapshot
Faster Fully Compressed Pattern Matching by Recompression
inferred← citeshttps://doi.org/10.1007/978-3-642-38771-5_2openalex-snapshot
Recompression: Word Equations and Beyond
inferred← citeshttps://doi.org/10.1007/978-3-642-38905-4_17openalex-snapshot
Approximation of Grammar-Based Compression via Recompression
inferred← citeshttps://doi.org/10.1007/978-3-642-39212-2_30openalex-snapshot
One-Variable Word Equations in Linear Time
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_37openalex-snapshot
Parallel Identity Testing for Skew Circuits with Big Powers and Applications
inferred← citeshttps://doi.org/10.1007/s00224-013-9443-6openalex-snapshot
The Complexity of Compressed Membership Problems for Finite Automata
inferred← citeshttps://doi.org/10.1007/s00224-019-09942-yopenalex-snapshot
Grammar-Based Compression of Unranked Trees
inferred← citeshttps://doi.org/10.1007/s00224-026-10266-xopenalex-snapshot
Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
inferred← citeshttps://doi.org/10.1007/s00453-014-9931-3openalex-snapshot
One-Variable Word Equations in Linear Time
inferred← citeshttps://doi.org/10.1007/s00453-020-00744-0openalex-snapshot
Dynamic and Internal Longest Common Substring
inferred← citeshttps://doi.org/10.1007/s00453-022-00996-yopenalex-snapshot
Fast and Simple Compact Hashing via Bucketing
inferred← citeshttps://doi.org/10.1007/s00453-023-01186-0openalex-snapshot
Near-Optimal Search Time in $$\delta $$-Optimal Space, and Vice Versa
inferred← citeshttps://doi.org/10.1007/s10044-002-0180-8openalex-snapshot
Faster algorithm of string comparison
inferred← citeshttps://doi.org/10.1016/j.dam.2019.01.014openalex-snapshot
Dynamic index and LZ factorization in compressed space
inferred← citeshttps://doi.org/10.1016/j.ic.2013.01.002openalex-snapshot
Isomorphism of regular trees and words
inferred← citeshttps://doi.org/10.1016/j.ic.2016.09.007openalex-snapshot
Approximation of smallest linear tree grammar
inferred← citeshttps://doi.org/10.1016/j.ic.2020.104518openalex-snapshot
A compressed dynamic self-index for highly repetitive text collections
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.05.027openalex-snapshot
Approximation of grammar-based compression via recompression
inferred← citeshttps://doi.org/10.1016/j.tcs.2026.115746openalex-snapshot
A textbook solution for dynamic strings
inferred← citeshttps://doi.org/10.1016/j.tcs.2026.116080openalex-snapshot
Grammar index by induced suffix sorting
inferred← citeshttps://doi.org/10.1016/s0304-3975(03)00142-7openalex-snapshot
Text sparsification via local maxima
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00024-8openalex-snapshot
An improved scheme for set equality testing and updating
inferred← citeshttps://doi.org/10.1109/dcc.2018.00037openalex-snapshot
A Dynamic Compressed Self-Index for Highly Repetitive Text Collections
inferred← citeshttps://doi.org/10.1109/dcc52660.2022.00014openalex-snapshot
FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00095openalex-snapshot
Faster Approximate Pattern Matching: A Unified Approach
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00098openalex-snapshot
Approximating Edit Distance in the Fully Dynamic Model
inferred← citeshttps://doi.org/10.1137/1.9781611973730.36openalex-snapshot
Internal Pattern Matching Queries in a Text and Applications
inferred← citeshttps://doi.org/10.1137/1.9781611975031.99openalex-snapshot
Optimal Dynamic Strings
inferred← citeshttps://doi.org/10.1137/1.9781611975994.37openalex-snapshot
Locally Consistent Parsing for Text Indexing in Small Space
inferred← citeshttps://doi.org/10.1137/1.9781611976496.5openalex-snapshot
Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets
inferred← citeshttps://doi.org/10.1137/1.9781611977073.112openalex-snapshot
How Compression and Approximation Affect Efficiency in String Distance Measures
inferred← citeshttps://doi.org/10.1137/21m1465706openalex-snapshot
Locally Consistent Parsing for Text Indexing in Small Space
inferred← citeshttps://doi.org/10.1137/23m1567618openalex-snapshot
Internal Pattern Matching Queries in a Text and Applications
inferred← citeshttps://doi.org/10.1142/s0218196715400056openalex-snapshot
SLP compression for solutions of equations with constraints in free and hyperbolic groups
inferred← citeshttps://doi.org/10.1142/s0218196718500431openalex-snapshot
Parallel identity testing for skew circuits with big powers and applications
inferred← citeshttps://doi.org/10.1145/1186810.1186812openalex-snapshot
The string edit distance matching problem with moves
inferred← citeshttps://doi.org/10.1145/2422436.2422468openalex-snapshot
Reachability in graph timelines
inferred← citeshttps://doi.org/10.1145/2631920openalex-snapshot
Faster Fully Compressed Pattern Matching by Recompression
inferred← citeshttps://doi.org/10.1145/2743014openalex-snapshot
Recompression
inferred← citeshttps://doi.org/10.1145/3055399.3055442openalex-snapshot
Randomized polynomial time identity testing for noncommutative circuits
inferred← citeshttps://doi.org/10.1145/3426473openalex-snapshot
Optimal-Time Dictionary-Compressed Indexes
inferred← citeshttps://doi.org/10.1145/3432999openalex-snapshot
Indexing Highly Repetitive String Collections, Part II
inferred← citeshttps://doi.org/10.1145/3452143.3465530openalex-snapshot
Cyclotomic Identity Testing and Applications
inferred← citeshttps://doi.org/10.1145/3519935.3520061openalex-snapshot
Dynamic suffix array with polylogarithmic queries and updates
inferred← citeshttps://doi.org/10.1145/3519935.3520070openalex-snapshot
An extendable data structure for incremental stable perfect hashing
inferred← citeshttps://doi.org/10.1145/3717823.3718168openalex-snapshot
Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
inferred← citeshttps://doi.org/10.1515/gcc-2012-0016openalex-snapshot
Algorithmics on SLP-compressed strings: A survey
inferred← citeshttps://doi.org/10.23638/lmcs-13(2:5)2017openalex-snapshot
Inter-procedural Two-Variable Herbrand Equalities
inferred← citeshttps://doi.org/10.26226/morressier.604907f41a80aac83ca25cc4openalex-snapshot
Work-sensitive Dynamic Complexity of Formal Languages
inferred← citeshttps://doi.org/10.4018/978-1-4666-5888-2.ch173openalex-snapshot
Indexing and Compressing Text
inferred← citeshttps://doi.org/10.4018/978-1-60566-026-4.ch302openalex-snapshot
Indexing Textual Information
inferred← citeshttps://doi.org/10.4018/978-1-60566-058-5.ch014openalex-snapshot
Indexing Textual Information
inferred← citeshttps://doi.org/10.4086/toc.2019.v015a007openalex-snapshot
inferred← citeshttps://doi.org/10.4230/lipics.approx/random.2022.32openalex-snapshot
Finding the KT Partition of a Weighted Graph in Near-Linear Time
inferred← citeshttps://doi.org/10.4230/lipics.cpm.2024.20openalex-snapshot
Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space
inferred← citeshttps://doi.org/10.4230/lipics.cpm.2024.3openalex-snapshot
Fully dynamic data structure for LCE queries in compressed space
inferred← citeshttps://doi.org/10.4230/lipics.esa.2019.6openalex-snapshot
Longest Common Substring Made Fully Dynamic
inferred← citeshttps://doi.org/10.4230/lipics.esa.2021.76openalex-snapshot
Faster Deterministic Modular Subset Sum
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2019.48openalex-snapshot
Faster Algorithms for All Pairs Non-Decreasing Paths Problem
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2019.37openalex-snapshot
Compressed Decision Problems in Hyperbolic Groups
inferred← citeshttps://doi.org/10.48550/arxiv.1109.3954openalex-snapshot
A Faster Grammar-Based Self-Index
inferred← citeshttps://doi.org/10.48550/arxiv.1111.3244openalex-snapshot
Faster fully compressed pattern matching by recompression
inferred← citeshttps://doi.org/10.48550/arxiv.1301.5842openalex-snapshot
Approximation of grammar-based compression via recompression
inferred← citeshttps://doi.org/10.48550/arxiv.1406.2348openalex-snapshot
Sampling the suffix array with minimizers
inferred← citeshttps://doi.org/10.48550/arxiv.1411.4157openalex-snapshot
A Polynomial Time Algorithm for Deciding Branching Bisimilarity on Totally Normed BPA
inferred← citeshttps://doi.org/10.48550/arxiv.1502.04545openalex-snapshot
Parallel Identity Testing for Skew Circuits with Big Powers and Applications
inferred← citeshttps://doi.org/10.48550/arxiv.1502.04625openalex-snapshot
Compressed Tree Canonization
inferred← citeshttps://doi.org/10.48550/arxiv.1504.06954openalex-snapshot
Dynamic index, LZ factorization, and LCE queries in compressed space
inferred← citeshttps://doi.org/10.48550/arxiv.1605.01079openalex-snapshot
Newer method of string comparison: the Modified Moving Contracting Window Pattern Algorithm
inferred← citeshttps://doi.org/10.48550/arxiv.1611.07235openalex-snapshot
Identity Testing for +-Regular Noncommutative Arithmetic Circuits
inferred← citeshttps://doi.org/10.48550/arxiv.2004.02781openalex-snapshot
Indexing Highly Repetitive String Collections
inferred← citeshttps://doi.org/10.48550/arxiv.2004.05309openalex-snapshot
Grammar-compressed Self-index with Lyndon Words
inferred← citeshttps://doi.org/10.5555/338219.338645openalex-snapshot
Pattern matching in dynamic texts
inferred← citeshttps://doi.org/10.5555/545381.545470openalex-snapshot
The string edit distance matching problem with moves
inferred← citeshttps://doi.org/10.82444/warw.33642484openalex-snapshot
Sequence distance embeddings
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.