## Séminaire Algorithmique |

Le séminaire a lieu **le mardi à 11 h 45** (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

# Résumé du séminaire du Mardi 28 Novembre 2017

*Improved bounds for testing Dyck languages*

## par 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).