# Improved bounds for testing Dyck languages

Frédéric Magniez (IRIF, Paris)We consider the problem of deciding membership in Dyck languages, a
fundamental family of context-free languages, comprised of well-balanced
strings of parentheses. In this problem we are given a string of length *n* in
the alphabet of parentheses of *m* types and must decide if it is well-
balanced. We consider this problem in the property testing setting, where one
would like to make the decision while querying as few characters of the input
as possible.

Property testing of strings for Dyck language membership for *m* = 1, with a
number of queries independent of the input size *n* , was provided in [Alon,
Krivelevich, Newman and Szegedy, SICOMP 2001]. Property testing of strings for
Dyck language membership for *m* ≥ 2 was first investigated in [Parnas, Ron
and Rubinfeld, RSA 2003]. They showed an upper bound and a lower bound for
distinguishing strings belonging to the language from strings that are far (in
terms of the Hamming distance) from the language, which are respectively (up
to polylogarithmic factors) the 2/3 power and the 1/11 power of the input size
*n*.

Here we improve the power of *n* in both bounds. For the upper bound, we
introduce a recursion technique, that together with a refinement of the
methods in the original work provides a test for any power of *n* larger than
2/5. For the lower bound, we introduce a new problem called Truestring
Equivalence, which is easily reducible to the 2-type Dyck language property
testing problem. For this new problem, we show a lower bound of *n* to the
power of 1/5.

Joint work with E. Fischer (Technion) and T. Starikovskaya (DIENS).