Name
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. |
Year | Venue | Field |
|---|---|---|
2016 | ESA | Discrete mathematics,Binary logarithm,Formal language,Property testing,Programming language,Streaming algorithm,Computer science,Correctness,Theoretical computer science,Pushdown automaton,Sampling (statistics),Regular language |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| nathanael francois | 1 | 0 | 0.34 |
| Frédéric Magniez | 2 | 570 | 44.33 |
| Michel De Rougemont | 3 | 138 | 143.69 |
| olivier serre | 4 | 288 | 22.02 |