Time+Place: Thursday 28/05/2015 15:30 Room 337-8 Taub Bld. Title: Streaming Property Testing of Visibly Pushdown Languages Speaker: Michel de Rougemont - SPECIAL LECTURE - Note unusual hour http://www.liafa.univ-paris-diderot.fr/~mdr/ Affiliation: University Paris II and LIAFA-CNRS Host: Johann Makowsky

### Abstract:


In the context of language recognition, we demonstrate the
superiority of streaming property testers against streaming algorithms
and property testers, when they are not combined.
Initiated by Feigenbaum a streaming property tester is a streaming
algorithm recognizing a language under the property testing
approximation: it must distinguish inputs of the language from those
that are $\eps$-far from it, while using the smallest possible memory
(rather than limiting its number of input queries).

Our main result is a streaming $\eps$-property tester for visibly
pushdown languages (\VPL{}) with one-sided error using memory space
$\mathrm{poly}((\log n) / \eps)$, important for the recognition of
regular unranked ordered trees.

This construction relies on a new (non-streaming) property tester for
weighted regular languages based on a previous tester by Alon {\it et
al}. We provide a simple application of this tester for streaming
testing special cases of instances of \VPL{} that are already hard for
both streaming algorithms and property testers.

(Joint work with Nathanael Francois, Frederic Magniez and Olivier Serre)

Short Bio:
Michel de Rougemont received his Ph.D. from UCLA in 1983 and his
Habilitation from University Paris South in 1988.
He is a Professor at University Paris II and part of LIAFA-CNRS.
He worked on finite Model theory, Databases and more recently on
approximate Algorithms.