Search Results

Documents authored by François, Nathanaël

Found 2 Possible Name Variants:

Francois, Nathanael

Document
DOI: 10.4230/LIPIcs.ESA.2016.43
Streaming Property Testing of Visibly Pushdown Languages

Authors: Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
In the context of formal 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 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 (V_{PL}) with memory space poly(log n /epsilon). Our construction is done in three steps. First, we simulate a visibly pushdown automaton in one pass using a stack of small height but whose items can be of linear size. In a second step, those items are replaced by small sketches. Those sketches rely on a notion of suffix-sampling we introduce. This sampling is the key idea for taking benefit of both streaming algorithms and property testers in the third step. Indeed, the last step relies on a (non-streaming) property tester for weighted regular languages based on a previous tester by Alon et al. This tester can directly be used for streaming testing special cases of instances of V_{PL} that are already hard for both streaming algorithms and property testers. We then use it to decide the correctness of completed items, given their sketches, before removing them from the stack.
Cite as

Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre. Streaming Property Testing of Visibly Pushdown Languages. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{francois_et_al:LIPIcs.ESA.2016.43,
  author =	{Fran\c{c}ois, Nathana\"{e}l and Magniez, Fr\'{e}d\'{e}ric and de Rougemont, Michel and Serre, Olivier},
  title =	{{Streaming Property Testing of Visibly Pushdown Languages}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.43},
  URN =		{urn:nbn:de:0030-drops-63559},
  doi =		{10.4230/LIPIcs.ESA.2016.43},
  annote =	{Keywords: Streaming Algorithm, Property Testing, Visibly Pushdown Languages}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.654
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting

Authors: Nathanaël François, Rahul Jain, and Frédéric Magniez

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
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 expansion, the ratio between the space used on the stream and the input size. We give tight bounds for the complexity of reversing a stream of length n in several of the possible models. In the read-only and write-only model, we show that p-pass algorithms need memory space Theta(n/p). But if either the output stream or the input stream is read-write, then the complexity falls to Theta(n/p^2). It becomes polylog(n) if p = O(log n) and both streams are read-write. We also study the complexity of sorting a stream and give two algorithms with small expansion. Our main sorting algorithm is randomized and has O(1) expansion, O(log n) passes and O(log n) memory.
Cite as

Nathanaël François, Rahul Jain, and Frédéric Magniez. Unidirectional Input/Output Streaming Complexity of Reversal and Sorting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 654-668, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{francois_et_al:LIPIcs.APPROX-RANDOM.2014.654,
  author =	{Fran\c{c}ois, Nathana\"{e}l and Jain, Rahul and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Unidirectional Input/Output Streaming Complexity of Reversal and Sorting}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{654--668},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.654},
  URN =		{urn:nbn:de:0030-drops-47298},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.654},
  annote =	{Keywords: Streaming Algorithms, Multiple Streams, Reversal, Sorting}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.454
Streaming Complexity of Checking Priority Queues

Authors: Nathanael Francois and Frédéric Magniez

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
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 a context of massive data, one would like to minimize both the amount of reliable memory of the checker and the number of passes on the sequence of operations. Chu, Kannan and McGregor (M. Chu, S. Kannan, and A. McGregor, 2007) initiated the study of checking priority queues in this setting. They showed that the use of timestamps allows to check a priority queue with a single pass and memory space \tilde{\Order}(\sqrt{N}). Later, Chakrabarti, Cormode, Kondapally and McGregor (A. Chakrabarti, G. Cormode, R. Kondapally, and A. McGregor, 2010) removed the use of timestamps, and proved that more passes do not help. We show that, even in the presence of timestamps, more passes do not help, solving an open problem of (M. Chu, S. Kannan, and A. McGregor, 2007; A. Chakrabarti, G. Cormode, R. Kondapally, and A. McGregor). On the other hand, we show that a second pass, but in reverse direction shrinks the memory space to \tilde{\Order}((\log N)^2), extending a phenomenon the first time observed by Magniez, Mathieu and Nayak (F. Magniez, C. Mathieu, and A. Nayak, 2010) for checking well-parenthesized expressions.
Cite as

Nathanael Francois and Frédéric Magniez. Streaming Complexity of Checking Priority Queues. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 454-465, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{francois_et_al:LIPIcs.STACS.2013.454,
  author =	{Francois, Nathanael and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Streaming Complexity of Checking Priority Queues}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{454--465},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.454},
  URN =		{urn:nbn:de:0030-drops-39561},
  doi =		{10.4230/LIPIcs.STACS.2013.454},
  annote =	{Keywords: Streaming Algorithms, Communication Complexity, Priority Queue}
}

François, Nathanaël

Document
DOI: 10.4230/LIPIcs.ESA.2016.43
Streaming Property Testing of Visibly Pushdown Languages

Authors: Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
In the context of formal 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 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 (V_{PL}) with memory space poly(log n /epsilon). Our construction is done in three steps. First, we simulate a visibly pushdown automaton in one pass using a stack of small height but whose items can be of linear size. In a second step, those items are replaced by small sketches. Those sketches rely on a notion of suffix-sampling we introduce. This sampling is the key idea for taking benefit of both streaming algorithms and property testers in the third step. Indeed, the last step relies on a (non-streaming) property tester for weighted regular languages based on a previous tester by Alon et al. This tester can directly be used for streaming testing special cases of instances of V_{PL} that are already hard for both streaming algorithms and property testers. We then use it to decide the correctness of completed items, given their sketches, before removing them from the stack.
Cite as

Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre. Streaming Property Testing of Visibly Pushdown Languages. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{francois_et_al:LIPIcs.ESA.2016.43,
  author =	{Fran\c{c}ois, Nathana\"{e}l and Magniez, Fr\'{e}d\'{e}ric and de Rougemont, Michel and Serre, Olivier},
  title =	{{Streaming Property Testing of Visibly Pushdown Languages}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.43},
  URN =		{urn:nbn:de:0030-drops-63559},
  doi =		{10.4230/LIPIcs.ESA.2016.43},
  annote =	{Keywords: Streaming Algorithm, Property Testing, Visibly Pushdown Languages}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.654
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting

Authors: Nathanaël François, Rahul Jain, and Frédéric Magniez

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
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 expansion, the ratio between the space used on the stream and the input size. We give tight bounds for the complexity of reversing a stream of length n in several of the possible models. In the read-only and write-only model, we show that p-pass algorithms need memory space Theta(n/p). But if either the output stream or the input stream is read-write, then the complexity falls to Theta(n/p^2). It becomes polylog(n) if p = O(log n) and both streams are read-write. We also study the complexity of sorting a stream and give two algorithms with small expansion. Our main sorting algorithm is randomized and has O(1) expansion, O(log n) passes and O(log n) memory.
Cite as

Nathanaël François, Rahul Jain, and Frédéric Magniez. Unidirectional Input/Output Streaming Complexity of Reversal and Sorting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 654-668, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{francois_et_al:LIPIcs.APPROX-RANDOM.2014.654,
  author =	{Fran\c{c}ois, Nathana\"{e}l and Jain, Rahul and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Unidirectional Input/Output Streaming Complexity of Reversal and Sorting}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{654--668},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.654},
  URN =		{urn:nbn:de:0030-drops-47298},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.654},
  annote =	{Keywords: Streaming Algorithms, Multiple Streams, Reversal, Sorting}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.454
Streaming Complexity of Checking Priority Queues

Authors: Nathanael Francois and Frédéric Magniez

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
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 a context of massive data, one would like to minimize both the amount of reliable memory of the checker and the number of passes on the sequence of operations. Chu, Kannan and McGregor (M. Chu, S. Kannan, and A. McGregor, 2007) initiated the study of checking priority queues in this setting. They showed that the use of timestamps allows to check a priority queue with a single pass and memory space \tilde{\Order}(\sqrt{N}). Later, Chakrabarti, Cormode, Kondapally and McGregor (A. Chakrabarti, G. Cormode, R. Kondapally, and A. McGregor, 2010) removed the use of timestamps, and proved that more passes do not help. We show that, even in the presence of timestamps, more passes do not help, solving an open problem of (M. Chu, S. Kannan, and A. McGregor, 2007; A. Chakrabarti, G. Cormode, R. Kondapally, and A. McGregor). On the other hand, we show that a second pass, but in reverse direction shrinks the memory space to \tilde{\Order}((\log N)^2), extending a phenomenon the first time observed by Magniez, Mathieu and Nayak (F. Magniez, C. Mathieu, and A. Nayak, 2010) for checking well-parenthesized expressions.
Cite as

Nathanael Francois and Frédéric Magniez. Streaming Complexity of Checking Priority Queues. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 454-465, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{francois_et_al:LIPIcs.STACS.2013.454,
  author =	{Francois, Nathanael and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Streaming Complexity of Checking Priority Queues}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{454--465},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.454},
  URN =		{urn:nbn:de:0030-drops-39561},
  doi =		{10.4230/LIPIcs.STACS.2013.454},
  annote =	{Keywords: Streaming Algorithms, Communication Complexity, Priority Queue}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact