3 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.DS2013
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
Nathanaël François, Rahul Jain, Frederic Magniez
We consider unidirectional data streams with restricted access, such as read-only and write-only streams. For read-write streams, we also introduce a new complexity measure called…
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…