1 Search Results for "de Rougemont, Michel"

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-dev.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}
}

Refine by Author
1 François, Nathanaël
1 Magniez, Frédéric
1 Serre, Olivier
1 de Rougemont, Michel

Refine by Classification

Refine by Keyword
1 Property Testing
1 Streaming Algorithm
1 Visibly Pushdown Languages

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "de Rougemont, Michel"

Streaming Property Testing of Visibly Pushdown Languages

Abstract

Cite as

Thanks for your feedback!

Could not send message