Skip to main navigation Skip to search Skip to main content

Streaming property testing of visibly pushdown languages

  • Nathanaël François
  • , Frédéric Magniez
  • , Michel De Rougemont
  • , Olivier Serre
  • University of Dortmund
  • Centre national de la recherche scientifique
  • Université Paris II

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

16 Citations (Scopus)

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 ϵ-far from it, while using the smallest possible memory (rather than limiting its number of input queries). Our main result is a streaming ϵ-property tester for visibly pushdown languages (VPL) with memory space poly((logn)/ϵ). 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 VPL 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.

Original languageEnglish
Title of host publication24th Annual European Symposium on Algorithms, ESA 2016
EditorsChristos Zaroliagis, Piotr Sankowski
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770156
DOIs
Publication statusPublished - 1 Aug 2016
Event24th Annual European Symposium on Algorithms, ESA 2016 - Aarhus, Denmark
Duration: 22 Aug 2016 → 24 Aug 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume57
ISSN (Print)1868-8969

Conference

Conference24th Annual European Symposium on Algorithms, ESA 2016
Country/TerritoryDenmark
CityAarhus
Period22/08/16 → 24/08/16

Keywords

  • Property testing
  • Streaming algorithm
  • Visibly pushdown languages

Fingerprint

Dive into the research topics of 'Streaming property testing of visibly pushdown languages'. Together they form a unique fingerprint.

Cite this