Near optimal limits found for testing balanced parentheses and string equality
Near-Optimal Bounds for Testing Residual-String Equality and Parenthesis Languages
Data Structures and Algorithms
Summary
The paper studies how hard it is to check if two special strings match when ignoring certain placeholder symbols, and if a sequence of parentheses is properly balanced. The authors sharpen previous estimates, showing nearly exact boundaries on the number of checks needed to test these properties efficiently. They also provide better methods for testing these conditions without changing their strategy based on earlier answers, improving speed and precision. Additionally, they reduce the complexity of how the testing depends on how close an input must be to being correct.
What this means in practice
- •For software testers: Optimize testing procedures for validating well-formed expressions in compilers and interpreters by understanding query limits of balanced parenthesis detection.
- •For data integrity engineers: Enhance algorithms that verify string equivalence under noise or placeholders with near-optimal query strategies derived from residual-string equality testing.
A theory result. No direct application yet.
Authors
Hadar Strauss
Abstract
Residual-String Equality, denoted $\texttt{ResStringEq}$, is the property consisting of all pairs of strings over $\{0,1,*\}$ that are equal after deleting all `$*$' symbols from them. This property was first introduced by Fischer, Magniez, and Starikovskaya (SODA 2018), who used it to show a lower bound on testing the $\texttt{Dyck}$ languages, where $\texttt{Dyck}_m$ is the language consisting of balanced sequences of parentheses over $m$ parenthesis types. They showed that testing $\texttt{ResStringEq}$ on inputs of length $n$ requires $Ω(n^{1/5})$ queries, and presented a reduction from testing $\texttt{ResStringEq}$ to testing $\texttt{Dyck}_m$ where $m \geq 2$. Furthermore, they showed that $\texttt{Dyck}_m$ can be tested with $O(n^{2/5+δ})$ queries for every constant proximity parameter, where $δ>0$ is an arbitrarily small constant. In this work, we nearly close the remaining gap, by showing that testing $\texttt{ResStringEq}$, and hence $\texttt{Dyck}_m$ where $m\geq 2$, requires $Ω(n^{2/5})$ queries. We also show a stronger lower bound of $Ω(\sqrt{n})$ for testers that make non-adaptive queries. We establish that the $Ω(\sqrt{n})$ bound is nearly tight, by presenting a non-adaptive tester for $\texttt{ResStringEq}$ that uses $O(n^{1/2+δ})$ queries for an arbitrarily small constant $δ>0$. Furthermore, we extend this non-adaptive tester to the $\texttt{Dyck}$ languages, with the same query complexity. Finally, we improve the dependence on the proximity parameter $ε$ in the tester of Fischer, Magniez, and Starikovskaya, reducing it from $O(1/ε)^{\mathrm{poly}(1/δ)}$ to $O(1/ε)^{O(\log(1/δ))}$.