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.