Metraipolis › archive › dc_e272889d43e6
Query Complexity of Testing Structured Parenthesis Languages — arXiv:2609.37431
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.37431
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T19:18:59.599Z
- SHA-256 of the archived text
12f7afc1fc68c20758d01f534686f79277490e57c6556ace764db496f91820af- Stable URL of this page
https://metraipolis.com/documento/dc_e272889d43e6
How to cite
Query Complexity of Testing Structured Parenthesis Languages — arXiv:2609.37431 — arXiv (en), https://arxiv.org/abs/2609.37431 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e272889d43e6 (Metraipolis archive dc_e272889d43e6, sha256 12f7afc1fc68c20758d01f534686f79277490e57c6556ace764db496f91820af)
BibTeX
@misc{dce272889d43e6,
title = {Query Complexity of Testing Structured Parenthesis Languages — arXiv:2609.37431},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.37431},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e272889d43e6; sha256 12f7afc1fc68c20758d01f534686f79277490e57c6556ace764db496f91820af},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.37431. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word and must distinguish valid inputs from words that are far in Hamming distance, while inspecting only a sublinear number of positions. Our results sharpen the boundary between constant-query testability and polynomial query complexity. First, we prove an $\Omega(n^{2/5})$ lower bound for testing Dyck languages $D_m$ with any fixed number $m\ge2$ of parenthesis types, improving the previous $\Omega(n^{1/5})$ lower bound of Fischer, Magniez, and Starikovskaya (SODA `18) and nearly matching their upper bound of $O(n^{2/5+o(1)})$. Furthermore, we show that all nonadaptive algorithms for these problems require $\Omega(n^{1/2})$ queries. Our lower bounds use a Pólya-urn process to construct the hard distribution; Second, we identify a broad class of weighted-parenthesis languages, which we call {\em excursion languages,} that remain constant-query testable. These languages encode bounded-step walks that stay nonnegative and return to zero. For every fixed excursion language, we give a nonadaptive tester with query complexity $O(1/\varepsilon^2)$, and we prove this dependence on $\varepsilon$ is optimal, even for adaptive algorithms. As a special case, we obtain the tight $\Theta(1/\varepsilon^2)$ query complexity of testing $D_1$, improving the previous $O(\log(1/\varepsilon)/\varepsilon^2)$ upper bound and giving the first matching two-sided-error lower bound. Third, we construct a simple hard language, Hidden String, that is generated by a deterministic linear grammar but nevertheless requires $\Omega(n^{2/5})$ adaptive queries and $\Omega(n^{1/2})$ nonadaptive queries to test. This shows that polynomial query complexity appears even for highly restricted string languages.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.37431 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T18:45:07.084Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).