Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NATHANAËL FRANÇOIS:
All reports by Author Nathanaël François:

TR15-104 | 13th May 2015
Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont

Streaming Property Testing of Visibly Pushdown Languages

Revisions: 2

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 et al, a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs ... more >>>


TR12-128 | 21st September 2012
Nathanaël François, Frederic Magniez

Streaming Complexity of Checking Priority Queues

Revisions: 1

This work is in the line of designing efficient checkers for testing the reliability of some massive data structures. Given a sequential access to the insert/extract operations on such a structure, one would like to decide, a posteriori only, if it corresponds to the evolution of a reliable structure. In ... more >>>




ISSN 1433-8092 | Imprint