2 papers
cs.DS2015
Streaming Property Testing of Visibly Pushdown Languages
Nathanaël François, Frédéric Magniez, Michel de Rougemont +1
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.…
cs.DS2012
Streaming Complexity of Checking Priority Queues
Nathanaël François, Frederic Magniez
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…