Fast Algorithms for Parsing Sequences of Parentheses with Few Errors
Summary: First algorithm to repair unbalanced-parentheses sequences in O(n) + d^{O(1)} time, i.e., linear in input size when minimum edit distance d is small, improving on cubic-time DP. Enables fast repair of semi-structured docs (XML/JSON) with few errors. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Arturs Backurs
- 2. Krzysztof Onak
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,845 | On Repairing Structural Problems In Semi-structured Data | 2013 | VLDB | 6.7073366e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,048 | On Repairing Timestamps for Regular Interval Time Series | 2022 | VLDB | 4.4039656e-05 |
| 10,081 | From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies | 2026 | SIGMOD | 4.1945683e-05 |
| 11,881 | Cleaning Timestamps with Temporal Constraints | 2016 | VLDB | 4.1945683e-05 |
| 265 | A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification | 2005 | SIGMOD | 0.00029763412 |
| 7,605 | The Computation of Optimal Subset Repairs | 2020 | VLDB | 4.697534e-05 |
| 10,511 | The Best of Both Worlds: On Repairing Timestamps and Attribute Values for Multivariate Time Series | 2025 | SIGMOD | 4.1945683e-05 |
| 12,102 | Deterministic Regular Expressions in Linear Time | 2012 | PODS | 4.1945683e-05 |
| 13,484 | Efficient Evaluation for a Temporal Logic on Changing XML Documents | 2011 | PODS | - |
| 9,301 | Repairing Data through Regular Expressions | 2016 | VLDB | 4.3587281e-05 |
| 3,845 | On Repairing Structural Problems In Semi-structured Data | 2013 | VLDB | 6.7073366e-05 |