Streaming Property Testing of Visibly Pushdown Languages *

DOI10.4230/LIPICS.ESA.2016.43MaRDI QIDQ4606314zbMATH OpenOpenAlexFDO

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

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1505.03334

zbMATH Keywords

property testingstreaming algorithmvisibly pushdown languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Randomized algorithms (68W20)

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 $mathrmpoly((logn)/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.

Recommendations

• On visibly pushdown trace languages
• Testing non-deterministic stream X-machine models and P systems
• Testing non-deterministic stream X-machine models and P systems
• Testing conformance to a quasi-non-deterministic stream X-machine
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• Visibly pushdown languages over sliding windows
• Automata, Languages and Programming
• Property testing of regular tree languages
• Testing confluence of nonterminating rewriting systems
• Testing conformance of a deterministic implementation against a non-deterministic stream X-machine

Cited in

(7)

• Automata theory on sliding windows
• Streaming algorithms for some problems in log-space
• Visibly pushdown languages over sliding windows
• Streamability of nested word transductions
• Regular languages in the sliding window model
• Streaming in graph products
• Property testing of regular languages with applications to streaming property testing of visibly pushdown languages

This page was built for publication: Streaming Property Testing of Visibly Pushdown Languages *

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606314)