Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR15-104 | 3rd November 2015 11:20

#### Streaming Property Testing of Visibly Pushdown Languages

Revision #2
Authors: Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont
Accepted on: 3rd November 2015 11:20
Keywords:

Abstract:

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. 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 $\varepsilon$-far from it, while using the smallest possible memory (rather than limiting its number of input queries).

Our main result is a streaming $\varepsilon$-property tester for visibly pushdown languages (VPL) with one-sided error using memory space $\mathrm{poly}((\log n) / \varepsilon)$.

This constructions relies on a (non-streaming) property tester for weighted regular languages based on a previous tester by Alon et al. We provide a simple application of this tester for streaming testing special cases of instances of VPL that are already hard for both streaming algorithms and property testers.

Our main algorithm is a combination of an original simulation of visibly pushdown automata using a stack with small height but possible items of linear size. In a second step, those items are replaced by small sketches. Those sketches relies on a notion of suffix-sampling we introduce. This sampling is the key idea connecting our streaming tester algorithm to property testers.

Changes to previous version:

Major modifications in the presentation.

Revision #1 to TR15-104 | 24th June 2015 15:19

#### Streaming Property Testing of Visibly Pushdown Languages

Revision #1
Authors: Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont
Accepted on: 24th June 2015 15:19
Keywords:

Abstract:

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. 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 $\varepsilon$-far from it, while using the smallest possible memory (rather than limiting its number of input queries).

Our main result is a streaming $\varepsilon$-property tester for visibly pushdown languages (VPL) with one-sided error using memory space $\mathrm{poly}((\log n) / \varepsilon)$.

This constructions relies on a new (non-streaming) property tester for weighted regular languages based on a previous tester by Alon et al. We provide a simple application of this tester for streaming testing special cases of instances of VPL that are already hard for both streaming algorithms and property testers.

Our main algorithm is a combination of an original simulation of visibly pushdown automata using a stack with small height but possible items of linear size. In a second step, those items are replaced by small sketches. Those sketches relies on a notion of suffix-sampling we introduce. This sampling is the key idea connecting our streaming tester algorithm to property testers.

Changes to previous version:

Minor typos have been fixed in the proof of Lemma 4.14

### Paper:

TR15-104 | 13th May 2015 13:30

#### Streaming Property Testing of Visibly Pushdown Languages

TR15-104
Authors: Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont
Publication: 23rd June 2015 02:59
Keywords:

Abstract:

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. 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 $\varepsilon$-far from it, while using the smallest possible memory (rather than limiting its number of input queries).

Our main result is a streaming $\varepsilon$-property tester for visibly pushdown languages (VPL) with one-sided error using memory space $\mathrm{poly}((\log n) / \varepsilon)$.

This constructions relies on a new (non-streaming) property tester for weighted regular languages based on a previous tester by Alon et al. We provide a simple application of this tester for streaming testing special cases of instances of VPL that are already hard for both streaming algorithms and property testers.

Our main algorithm is a combination of an original simulation of visibly pushdown automata using a stack with small height but possible items of linear size. In a second step, those items are replaced by small sketches. Those sketches relies on a notion of suffix-sampling we introduce. This sampling is the key idea connecting our streaming tester algorithm to property testers.

ISSN 1433-8092 | Imprint