Residual-String Equality, denoted $\text{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 $\text{Dyck}$ languages, where $\text{Dyck}_m$ is the language consisting of balanced sequences of parentheses over $m$ parenthesis types. They showed that testing $\text{ResStringEq}$ on inputs of length $n$ requires $\Omega(n^{1/5})$ queries, and presented a reduction from testing $\text{ResStringEq}$ to testing $\text{Dyck}_m$ for any $m \geq 2$. Furthermore, they showed that $\text{Dyck}_m$ can be tested with $O(n^{2/5+\delta})$ queries for every constant proximity parameter, where $\delta>0$ is an arbitrarily small constant.

In this work, we nearly close the gap, by showing that testing $\text{ResStringEq}$, and hence $\text{Dyck}_m$ (for any $m\geq 2$), requires $\Omega(n^{2/5})$ queries. We also show a stronger lower bound of $\Omega(\sqrt{n})$ for testers that make non-adaptive queries. We establish that the $\Omega(\sqrt{n})$ bound is nearly tight, by presenting a non-adaptive tester for $\text{ResStringEq}$ that uses $O(n^{1/2+\delta})$ queries for an arbitrarily small constant $\delta>0$. Furthermore, we extend this non-adaptive tester to the $\text{Dyck}$ languages, with the same query complexity. Finally, we improve the dependence on the proximity parameter $\epsilon$ in the tester of Fischer, Magniez, and Starikovskaya, reducing it from $O(1/\epsilon)^{\mathrm{poly}(1/\delta)}$ to $O(1/\epsilon)^{O(\log(1/\delta))}$.