Query Complexity of Testing Structured Parenthesis Languages

arXiv:2609.37431 · cs.DS, cs.CC · Submitted 2026-09-29 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Query Complexity of Testing Structured Parenthesis Languages".

Jane: Here's the gist of the paper. We study the query complexity of testing membership in structured string languages, with a focus on Dyck languages and their natural generalizations The results sharpen the boundary between constant-query testability and polynomial query complexity Lower Bounds for Structured Languages The paper establishes lower bounds for testing Dyck languages with multiple parenthesis types, showing an improved bound from omega(n1/5) to omega(n2⁄5) for adaptive testers and a nonadaptive lower bound of omega(n1/2) queries Furthermore, the authors construct a hard language called HiddenString that requires both omega(n2⁄5) adaptive queries and omega(n1/2) nonadaptive queries to test This demonstrates that polynomial query complexity appears even for highly restricted string languages generated by deterministic linear grammars.

Tom: Excursion Languages and Optimal Testing The authors identify a broad class of weighted-parenthesis languages called excursion languages, which retain the constant-query testability of D1 They prove that all excursion languages are testable with O(1/ε2) queries by nonadaptive algorithms, and this bound is optimal even for adaptive algorithms.

Jane: Specifically, they obtain the tight Θ(1/ε2) query complexity of testing D1.

Tom: Implications for Dyck-m Languages The results imply that for every fixed m ≥ 2, testing the Dyck-m language Dm requires omega(n2⁄5) queries adaptively and omega(n1/2) queries nonadaptively.

Title and authors: Tom: So, we're looking at this paper right now, "Query Complexity of Testing Structured Parenthesis Languages," and the title tells you immediately we're talking about how hard it is to test if a string belongs to these structured languages.

Jane: Exactly. It focuses on Dyck languages and their generalizations, which are basically strings with balanced parentheses, and it aims to sharpen the boundary between constant-query testability and polynomial query complexity.

Lu: The authors are Tim Jackman, Diptaksho Palit, and Sofya Raskhodnikova. They're digging into property testing using query access to a word.

Meng: So what does this actually mean for us in terms of what we can practically test? Does it just confirm that Dyck languages are hard to test?

Tom: It does more than confirm hardness; they establish some new, tighter lower bounds for testing these languages. Specifically, they show a lower bound of Omega of n two-fifths for testing Dyck languages Dm with any fixed number m greater than or equal to two types of parentheses.

Jane: That's a big improvement over older results, which were showing a bound of Omega of n one-fifth. It’s like they tightened the fence on how many queries you can use before you definitely need more than just a constant amount.

Lalam: From my perspective in terms of what this means for the literature, it solidifies the separation between Dyck-one and Dyck languages with multiple types of parentheses.

Tom: Right, so the main implication is that D1, which has constant-query testers, is fundamentally different from testing any Dm where m is two or more.

Lu: It also highlights that this separation holds even when we look at adaptive testers, showing they need Omega of n two-fifths queries in that case.

Meng: That’s useful for us because it sets a clear complexity floor; if you're testing a language like D2, you're looking at roughly n two-fifths queries minimum.

The paper's summary: Jane: Now, the paper summarizes the main findings of "Query Complexity of Testing Structured Parenthesis Languages," which essentially boils down to showing that for Dyck languages with multiple types of parentheses, there's a clear polynomial complexity barrier.

Tom: They prove an Omega of n two-fifths lower bound for testing Dyck languages Dm where m is any fixed number greater than or equal to two parenthesis types. That’s the adaptive case they are focusing on right now.

Lu: And they also show that all nonadaptive algorithms for these problems require Omega of n one-half queries. That means you can't avoid a certain amount of queries even if you aren't making choices based on previous results.

Meng: So, the summary is essentially: adaptive testing needs n two-fifths, and nonadaptive testing needs n one-half for these harder Dyck languages. That’s the core complexity result they are highlighting here.

Jane: And they build this up by showing that this bound is tighter than what was previously known, improving on earlier work from Fischer, Magniez, and Starikovskaya.

Tom: It's important to remember that their nonadaptive lower bound for HiddenString—a related hard language—is Omega of n one-half queries for strings of length three n.

Lu: That connection is key because they reduce the testing problem for Dyck languages Dm where m is two or more down to testing HiddenString, which already has a known nonadaptive lower bound of Omega of n one-half queries.

Jane: So, even though we're talking about parenthesis types, the underlying difficulty seems tied to this specific nonadaptive query constraint.

Meng: From an engineering standpoint, if we were building a tester for D2 or higher, we’d know upfront that our nonadaptive approach would need at least n one-half queries to be guaranteed to work.

The paper's improvements: Tom: The paper really highlights the improvements they made over previous results by pushing the lower bound from Omega of n one-fifth up to Omega of n two-fifths for adaptive testers.

Jane: And that’s paired with a new nonadaptive lower bound, which is Omega of n one-half queries for those same Dyck languages Dm with m greater than or equal to two types of parentheses.

Lu: They also identified a whole class of weighted-parenthesis languages called excursion languages, and they showed these retain the constant-query testability property of Dyck one.

Meng: That's interesting because if you can show that an entire family like excursion languages is constant query testable, it simplifies the landscape for those specific structures.

Tom: And they proved that testing all those excursion languages requires only a bound of Omega of n one-half queries nonadaptively. That’s a strong statement about the structure of these languages.

Jane: But maybe the most concrete improvement is for Dyck one itself, where they achieved an optimal query complexity of Theta of one over epsilon squared for testing D1.

Tom: That's a huge deal because that matches the lower bound derived from distinguishing distributions, meaning their tester isn't just good; it’s as good as theoretically possible for that setup.

Lu: And they showed the optimality of their testers by proving that for Dyck one, every adaptive epsilon tester has query complexity Omega of one over epsilon squared queries.

Conclusion: Jane: So, to wrap up on "Query Complexity of Testing Structured Parenthesis Languages," we've seen that while D1 is testable with constant queries, testing Dyck languages with two or more types requires a polynomial query complexity bound.

Tom: The main conclusion is that the boundary between constant-query and polynomial-query testability for these structures is really sharp. We have a clear separation based on the number of parenthesis types involved.

Lu: It confirms that even restricted classes like linear languages, specifically the Nasu–Honda deterministic linear languages, require Omega of n two-fifths adaptively and Omega of n one-half nonadaptively queries to test.

Meng: From a production standpoint, this means if you're dealing with these multi-type structures in a real system, you need to budget for that polynomial query complexity when you can't rely on constant time.

Lalam: And Lalam is sure about this: they’ve shown that even for excursion languages, the optimal query complexity is Theta of one over epsilon squared queries, which is the tight bound.

Jane: It really paints a picture of where we stand now in sublinear algorithms for context-free languages and sets up some interesting open questions about what's out there next.

Tom: We’re leaving that paper here on "Query Complexity of Testing Structured Parenthesis Languages," and it shows us exactly how structural properties dictate the complexity of testing.

Boston University

cs.DS, cs.CC

Submitted: 2026-09-29

Updated: 2026-11-10

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 84/100

The gist: We study the query complexity of testing membership in structured string languages, with a focus on Dyck languages and their natural generalizations The results sharpen the boundary between…

Key concepts

Dyck Languages (Dm)
These are strings of parentheses with multiple types that must be perfectly balanced. They are generated by specific rules and are a fundamental class of structured string languages studied in this context. Testing them involves checking if the string is well-formed.
Excursion Languages (Lℓ,r)
These languages describe paths on an integer line that start at zero, never go below zero, and return to zero. They are a specific type of deterministic one-counter language that exhibit constant-query testability with optimal bounds for testing.
HiddenString
This is a hard language constructed specifically to show high query complexity requirements. It involves transformations where the true string relates to the reverse of a modified version of the input, serving as a benchmark for testing difficulty.

Terminology

Summary

We study the query complexity of testing membership in structured string languages, with a focus on Dyck languages and their natural generalizations The results sharpen the boundary between constant-query testability and polynomial query complexity

Lower Bounds for Structured Languages

The paper establishes lower bounds for testing Dyck languages with multiple parenthesis types, showing an improved bound from omega(n1/5) to omega(n2⁄5) for adaptive testers and a nonadaptive lower bound of omega(n1/2) queries Furthermore, the authors construct a hard language called HiddenString that requires both omega(n2⁄5) adaptive queries and omega(n1/2) nonadaptive queries to test This demonstrates that polynomial query complexity appears even for highly restricted string languages generated by deterministic linear grammars.

Excursion Languages and Optimal Testing

The authors identify a broad class of weighted-parenthesis languages called excursion languages, which retain the constant-query testability of D1 They prove that all excursion languages are testable with O(1/ε2) queries by nonadaptive algorithms, and this bound is optimal even for adaptive algorithms. Specifically, they obtain the tight Θ(1/ε2) query complexity of testing D1. p. 0

Implications for Dyck-m Languages

The results imply that for every fixed m ≥ 2, testing the Dyck-m language Dm requires omega(n2⁄5) queries adaptively and omega(n1/2) queries nonadaptively. This is derived by reducing the problem from testing D2 to testing HiddenString

Testing Excursion Languages and Dyck-1

The paper provides an algorithm for excursion languages and its analysis, which derives a tight upper bound for the Dyck-1 language The tester for D1 achieves O(1/ε2) queries, matching the lower bound derived from distinguishing distributions.

Linear Languages and Hierarchy

The authors show that polynomial query complexity arises within a very restricted subclass of linear languages, specifically the Nasu–Honda deterministic linear languages This language requires omega(n2⁄5) adaptive queries and omega(n1/2) nonadaptive queries to test.

Optimality of Testers

The authors prove the optimality of their testers by showing that for D1, every (two-sided error, adaptive) ε-tester has query complexity omega(1/ε2), matching the lower bound. Similarly, they show that for all excursion languages Ll,r, the optimal query complexity is Θ(1/ε2). p. 1

Relationship Between Language Classes

The paper situates its results within the broader context of property testing by illustrating a hierarchy of language classes recognized by nondeterministic biautomata It shows that the class of linear languages contains a language requiring omega(n2⁄5) queries to test, sitting at the bottom of this hierarchy.

Known Query Complexity Bounds

The paper summarizes known query complexity bounds for various language classes, showing that regular languages have constant query complexity while Dyck languages require omega(n2⁄5) queries adaptively and omega(n1/2) nonadaptively. It also notes that deterministic one-counter languages contain languages requiring omega(log log n) queries. p. 3

Open Questions

The paper leaves open the broader question of how hard CFL membership testing can be, and whether every CFL is testable with O(√n)·poly(1/ε) queries. It also questions whether there is a CFL whose testing complexity is polynomially larger, perhaps even linear in n. p. 7

Organization

The paper organizes its results by presenting lower bounds for HiddenString and Dyck-m languages first Then it gives the tester for excursion languages and the Dyck-1 language Finally, it shows the optimality of their testers through lower bounds.

Preliminaries

The preliminaries define fundamental concepts such as alphabet, word length, and Hamming distance between words Definition 2.1 defines an ε-far string and a (two-sided) ε-tester Definition 2. p. 72 defines Dyck languages Dm based on opening and closing parenthesis types. p. 8

Dyck Languages

The Dyck language Dm consists of all well-balanced strings of parentheses with m types, generated by S → λ SS tLS tR The query complexity of testing Dyck languages has been studied since the early work on property testing.

Excursion Languages

Excursion languages Ll,r are defined as walks on the integer line that start at height 0, stay nonnegative, and return to 0 They form a simple family of deterministic one-counter languages.

Hidden String

The language HiddenString is defined over the alphabet with a star symbol, where T(w) is obtained by deleting all ⋆ symbols and H(w) adds an H superscript The true-string T(u) equals H(v rev).

Lower Bounds for Hidden String and Dyck-m for m ≥ 2

The lower bounds for HiddenString are stated and proved in Section 3.1 in Theorems 3. p. 28 and 3.15 These theorems are used to derive Theorems 1. p. 81 and 1.4.

Adaptive Lower Bound for HiddenString

Theorem 3.8 states that every adaptive ε-tester for HiddenString has query complexity omega(n2⁄5) on strings of length 3n The proof uses Yao’s minimax principle to show that D+ and D− are hard to distinguish with o(n2⁄5) queries. p. 8

Nonadaptive Lower Bound for HiddenString

Theorem 3.15 states that every nonadaptive ε-tester for HiddenString has query complexity omega(n1/2) on strings of length 3n The proof uses a P´olya-urn process in the construction of the hard distribution. p. 0

Implications for Dyck languages

The results show that every Dyck language Dm for m ≥ 2 requires omega(n2⁄5) queries to test adaptively and omega(n1/2) queries to test nonadaptively This is derived from Theorem 3.8 and Theorem 3. p. 215 using a reduction between testing D2 and HiddenString. p. 7

Implications for Linear Languages

The authors show that polynomial query complexity arises even within a very restricted subclass of linear languages, namely the Nasu–Honda deterministic linear languages This language requires omega(n2⁄5) adaptive queries and omega(n1/2) nonadaptive queries to test.

Testing Excursion Languages and the Dyck-1 Language

The authors give an algorithm for the excursion languages and Dyck-1, proving a nonadaptive tester makes O(ρ2⁄ε2) queries where ρ = max≤l, r The tester for D1 achieves O(1/ε2) queries, matching the lower bound derived from distinguishing distributions.

The authors show that their testers in Section 4 have optimal query complexity by matching the dependence on ε in the lower bounds for D1 and excursion languages

Lower Bound for Dyck-1 Language

Theorem 5.1 states that every (two-sided error, adaptive) ε-tester for D1 has query complexity omega(1/ε2) This is proven by reducing the problem to distinguishing distributions H0 and H1. p. 0

Lower Bound for All Excursion Languages

Theorem 5.3 states that every (two-sided error, adaptive) ε-tester for Ll,r has query complexity omega(1/ε2) This is proven by reducing from the distinguishing problem in Theorem 5. p. 02.

Distinguishing Lower Bound

Lemma 5.2 states that every deterministic algorithm with query access to a string w ∈ (−1, 1)m requires omega(1/γ2) queries to distinguish between w ∼ H0 and w ∼ H1 This is based on the sampling-without-replacement versus sampling-with-replacement bound. p. 0

Anti-concentration Bounds

Lemma B.1 provides a bound on the probability that the sum of independent uniform random variables equals a specific value, showing Pr [Ps i=1 Yi = t] ≤ 1/√s This is used in proving Theorem 3.13.

C Testability and Relationships of Subclasses of CFLs

The paper situates its results within the broader context of property testing by illustrating a hierarchy of language classes recognized by nondeterministic biautomata It shows that even very restricted classes of context-free languages may not be testable.

Hierarchy of Language Classes

Figure 5 illustrates the relationships between these classes, collecting known query complexity bounds, showing that linear languages contain a language requiring omega(n2⁄5) queries to test This result shows that even very restricted classes of context-free languages may not be testable.

Appendix C. p. 3 p. 3 p. 31 The Nondeterministic Biautomata Hierarchy

The hierarchy of language classes can be characterized using nondeterministic biautomata, and the class DBWP contains the Nasu–Honda deterministic linear languages at the bottom

Appendix C.2 Known Query Complexity Bounds for Subclasses of CFLs

The paper surveys known query complexity bounds for subclasses of CFLs, noting that regular languages sit as a testable core inside the context-free languages It also notes that deterministic one-counter languages contain languages requiring omega(log log n) queries.

References

The paper lists numerous references supporting its claims, including work by Alon et al. [AKNS00] and Fischer, Magniez, and Starikovskaya [FMS18] It also includes foundational work on property testing like [GGR98] and results on counter automata like [GV13] The references cover topics such as regular languages, context-free languages, and linear grammars. p. 1

Tail Bounds and Yao’s Principle

The paper uses tail bounds in its proof of Theorem 4.2 to show that the sampled estimate is unlikely to substantially underestimate the true distance It also uses Yao’s principle adapted from [RS06] to prove lower bounds on query complexity. p. 6

The paper uses anti-concentration bounds in its proof of Theorem 3.13 to show that the probability of a sum of uniform random variables equaling a specific value is bounded by 5b√s This technique is crucial for bounding the query complexity.

Conclusion

The paper concludes that the authors have sharpened the boundary between constant-query and polynomial-query testability for several natural subclasses of CFLs They also show that even very restricted linear languages can require polynomially many queries to test. The overall contribution is a deeper understanding of the structural reasons behind the mixture of constant-query and polynomial-query phenomena in CFLs. p. 1

The hierarchy of linear languages can be characterized using nondeterministic biautomata, and the class DBWP contains the Nasu–Honda deterministic linear languages at the bottom

The paper surveys known query complexity bounds for subclasses of CFLs, noting that regular languages sit as a testable core inside the context-free languages It also notes that deterministic one-counter languages contain languages requiring omega(log log n) queries

The paper uses tail bounds in its proof of Theorem 4.2 to show that the sampled estimate is unlikely to substantially underestimate the true distance It also uses Yao’s principle adapted from [RS06] to prove lower bounds on query complexity

The paper concludes that the authors have sharpened the boundary between constant-query and polynomial-query testability for several natural subclasses of CFLs They also show that even very restricted linear languages can require polynomially many queries to test The overall contribution is a deeper understanding of the structural reasons behind the mixture of constant-query and polynomial-query phenomena in CFLs.

**Appendix C.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved testability of Dyck languages with multiple parenthesis types: The system can now distinguish between constant-query testable Dyck-1 language (D1) and Dyck languages Dm for m greater than or equal to 2, as "D1 has constant-query testers, whereas testing Dm for every fixed m >= 2 requires Omega(n 2/5) queries."

  2. Improved nonadaptive query complexity for Dyck languages: The system can now achieve a tight bound of Omega(n 1/2) queries for testing any Dyck language Dm with m greater than or equal to 2, improving previous bounds and establishing a clear separation between adaptive and nonadaptive testing for these languages.

  3. Improved testability for excursion languages: The system can now perform constant-query testing on all excursion languages Ll,r with O(1/epsilon 2) queries for both adaptive and nonadaptive algorithms, which is optimal, even for adaptive algorithms.

  4. Improved testability of Dyck-1 language: The system can now achieve an optimal query complexity of Theta(1/epsilon 2) for testing the Dyck-1 language (D1), improving the previous O(log(1/epsilon)/epsilon 2) upper bound and providing a matching two-sided error lower bound.

  5. Improved detection of hard linear languages: The system can now detect membership in restricted deterministic linear languages, such as HiddenString⋄, which requires Omega(n 2/5) adaptive queries and Omega(n 1/2) nonadaptive queries to test, showing that polynomial query complexity appears even for highly restricted string languages.

  6. Improved understanding of the hierarchy of CFLs: The system can now situate known query complexity bounds within a hierarchy of linear languages, demonstrating that even very restricted classes of context-free languages may not be testable by placing HiddenString⋄ at the bottom level DBWP.

Related papers