2026-07-22T13:49:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14188 2024-03-06T10:53:42Z ddc:004 open_access

Property Testing of Regular Languages with Applications to Streaming Property Testing of Visibly Pushdown Languages Bathie, Gabriel Starikovskaya, Tatiana property testing regular languages streaming algorithms visibly pushdown languages In this work, we revisit the problem of testing membership in regular languages, first studied by Alon et al. [Alon et al., 2001]. We develop a one-sided error property tester for regular languages under weighted edit distance that makes 𝒪(ε^{-1} log(1/ε)) non-adaptive queries, assuming that the language is described by an automaton of constant size. Moreover, we show a matching lower bound, essentially closing the problem for the edit distance. As an application, we improve the space bound of the current best streaming property testing algorithm for visibly pushdown languages from 𝒪(ε^{-4} log⁶ n) to 𝒪(ε^{-3} log⁵ n log log n), where n is the size of the input. Finally, we provide a Ω(max(ε^{-1}, log n)) lower bound on the memory necessary to test visibly pushdown languages in the streaming model, significantly narrowing the gap between the known bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gabriel Bathie and Tatiana Starikovskaya 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.119 urn:nbn:de:0030-drops-141881 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.119 eng https://creativecommons.org/licenses/by/4.0/legalcode