PaperlayerView exact revision on arXiv

Source-linked AI summary

Query Complexity of Testing Structured Parenthesis Languages

Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova

arXiv:2609.37431v1cs.DScs.CC

TL;DR

The paper asks when structured-language membership can be tested with few position queries, despite the contrasting behavior already seen among context-free languages. It develops lower-bound constructions and an excursion-language tester, proving polynomial lower bounds for multi-type Dyck languages and HiddenString⋄ alongside tight ε-dependent bounds for excursion languages.

  • Problem

    Although D_1 has a constant-query tester and D_2 does not, the structural reasons that some context-free languages are easy to test while others need polynomially many queries remain unclear.

    Source: §1 · p. 2

  • Method

    The paper develops adaptive and nonadaptive hard distributions for lower bounds and tests excursion languages by estimating a statistic of the walk encoded by the input.

    Source: §1 · p. 2, Adaptive lower bound · p. 6, Nonadaptive lower bound · p. 7

  • Results

    For every fixed m ≥2, D_m testing requires Ω(n^2/5) queries and nonadaptive testing requires Ω(n^1/2); excursion languages have tight Θ(1/ε^2) complexity, and HiddenString⋄ has Ω(n^2/5) adaptive and Ω(n^1/2) nonadaptive lower bounds.

    Source: §1.1 · pp. 3–5

  • Takeaways & Limitations

    The results sharpen the boundary between constant-query and polynomial-query testability: excursion languages remain efficiently testable, while even a Nasu–Honda deterministic linear language can require polynomially many queries.

    Source: §1 · p. 2, §1.1 · p. 5

    The correct nonadaptive query-complexity exponent for testing D_m with m ≥2 remains open between Ω(n^1/2) and the trivial O(n) upper bound.

    Source: §1.4 · p. 7

Abstract

from arXiv · show

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\'olya-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.

1 Introduction

The paper sharpens the boundary between constant-query and polynomial-query testing for structured languages. It strengthens lower bounds for multi-type Dyck languages and identifies both testable excursion languages and a highly restricted hard language.

1 Introduction

  • The work studies when context-free language membership can be tested with few position queries, against a background where regular languages have constant-query testers but CFL behavior varies.Earlier results established constant-query testability for D_1 but not D_2, while the structural reasons for this difference remained unclear.Source: §1 · p. 2

1.3 Prior work

  • Prior work established a constant-query tester for D_1 and polynomial lower bounds for multi-type Dyck languages, but the structural boundary among CFL subclasses remained poorly understood.Earlier multi-type Dyck bounds included an Ω(n^1/5) lower bound and an O(n^2/5+α) upper bound for every α > 0 [FMS18].Source: §1 · p. 2, §1.1 · p. 3, §1.3 · p. 7

1.1 Our results

  • For every fixed m ≥2, testing D_m requires Ω(n^2/5) queries, and nonadaptive testers require Ω(n^1/2), strengthening the separation from D_1.The adaptive lower bound nearly matches the O(n^2/5+α) upper bound for every α > 0 from [FMS18].Source: §1.1 · p. 3
  • Every fixed excursion language has tight Θ(1/ε^2) query complexity for adaptive and nonadaptive testing; this also gives the optimal O(1/ε^2) tester for D_1.Excursion words encode bounded-weight steps whose walks stay nonnegative and return to zero.Source: §1.1 · pp. 3–4, Nonadaptive lower bound · p. 7
  • HiddenString⋄, a Nasu–Honda deterministic linear language, requires Ω(n^2/5) adaptive and Ω(n^1/2) nonadaptive queries to test.Its membership structure is a hidden marked reverse paired with a clear binary string.Source: §1.1 · pp. 4–5

Adaptive lower bound.

  • Adaptive lower bounds combine amortized analysis of tester progress with a reveal condition that exposes only nearby query collections whose total advance is proportional to their size.The hard instances use blockwise random star filters to increase uncertainty about alignments.Source: Adaptive lower bound · pp. 5–6

Nonadaptive lower bound.

  • For nonadaptive bounds, a Pólya-urn description of the weighted filter bounds the chance of finding matching pairs; the excursion tester instead estimates a walk statistic from O(1/ε^2) sampled positions.The statistic combines final height and minimum height to capture an incorrect endpoint or a dip below zero.Source: Nonadaptive lower bound · pp. 6–7

1.4 Open questions

  • The results leave open the correct nonadaptive exponent for multi-type Dyck testing and the broader worst-case query complexity of CFL membership testing.The paper also poses the problem of characterizing which natural CFL subclasses have constant, polylogarithmic, polynomial, or near-linear query complexity.Source: §1.4 · pp. 7–8

2 Preliminaries

The preliminaries establish notation for words and languages, define Hamming distance and the tester guarantee, and introduce Dyck languages.

2 Preliminaries

  • A word is a finite string over an alphabet Σ, a language is a subset of Σ*, and ◦ denotes concatenation.The notation [[a]]_n denotes n copies of a symbol a.Source: §2 · p. 8
  • The distance between equal-length words is their Hamming distance, and distance to a language is the minimum such distance to a same-length member.A word is ε-far from a language when every same-length member differs from it in at least εn positions.Source: §2 · p. 8
  • An ε-tester accepts members and rejects words ε-far from the language, each with probability at least 2/3.A tester is adaptive when its queries can depend on earlier answers; testability means query complexity can depend on ε but not input length.Source: §2 · p. 8
  • The notation [n] denotes {1, 2, …, n}, and D_m is introduced as a language over symbols for opening and closing parentheses of m types.The supplied definition identifies Γ_m as the alphabet containing the typed opening and closing symbols.Source: §2 · pp. 8–9

3 Lower bounds for Hidden String and Dyck-m for m ≥2

This section develops a hard-distribution framework for HiddenString and proves adaptive and nonadaptive query lower bounds for testing it. It also transfers the bounds to every Dyck language Dm for m ≥ 2 and considers a related deterministic linear language.

3.1 Lower bound for HiddenString

  • HiddenString uses superscript-H symbols to protect distance comparisons, while its design choices ensure it is a CFL and HiddenString⋄ is a Nasu–Honda linear language.The clear string contains no ⋆ symbols in HiddenString⋄; the paper contrasts these constraints with TruestringEquivalence [FMS18].Source: §3.1 · p. 9
  • The hard distributions place D+ inside HiddenString and make D− 1/720-far from it with probability 1−o(1).They share the hidden-string construction; D− is formed by resampling the middle third of the clear string.Source: §3.1 · p. 10

3.1.1 Adaptive lower bound

  • For sufficiently small constant ε, every adaptive ε-tester for HiddenString on length-3n strings needs Ω(n^2/5) queries.The proof uses block filters with block length n^3/5 and shows the bad event controlling distinguishability occurs with probability o(1).Source: §3.1.1 · pp. 12, 14
  • The filter distribution sets b := n3/5, partitions [n] into consecutive length-b blocks, and samples a uniform weight and uniformly random subset of that size per block; hmax tracks revealed whole-block frontiers.Source: §3.1.1 · p. 12
  • With o(n^2/5) adaptive queries, D+ and D− are hard to distinguish; expected total advance is o(n), and the probability it exceeds n/3 is o(1).The proof uses Yao’s minimax principle.Source: §3.1.1 · pp. 15–16

3.1.2 Nonadaptive lower bound

  • Ω(n^1/2) queries are necessary for every nonadaptive ε-tester for HiddenString, for all sufficiently small constant ε.The proof bounds the probability of BAD by o(1) using a union bound; the filter bits can be generated by a Pólya urn process.Source: §3.1.2 · pp. 16–17

3.2 Implications for Dyck languages

  • For every m ≥2, Dm requires Ω(n^2/5) adaptive and Ω(n^1/2) nonadaptive queries, by reduction to HiddenString.The reduction preserves nonadaptivity and transfers tester query complexity with a constant-factor change in distance parameter and input length.Source: §3.2 · pp. 17–18

3.3 Implications for linear languages

  • HiddenString⋄ requires Ω(n^2/5) adaptive and Ω(n^1/2) nonadaptive queries, yet is a Nasu–Honda deterministic linear language.The hard distributions extend by inserting ⋄ between the hidden and clear strings; its grammar productions satisfy the required form and determinism condition.Source: §3.3 · p. 18

4 Testing excursion languages and the Dyck-1 language

The section defines excursion languages as bounded-step walks that stay nonnegative and return to zero, then gives a nonadaptive tester with query complexity O(ρ^2/ε^2). A repair lemma relates distance to a walk’s final and minimum sums, supporting the tester’s analysis and its application to D1.

4 Testing excursion languages and the Dyck-1 language

  • O(ρ^2/ε^2) queries suffice for a nonadaptive ε-tester for every fixed excursion language Lℓ,r, where ρ = max{ℓ, r}.For sufficiently small inputs the tester queries the entire word and decides membership exactly.Source: §4 · p. 19, §4.2 · p. 23

4.2 Analysis of the tester for excursion languages

  • The tester samples positions, estimates ∆(w) = s(w) − 2m(w), and rejects when the estimate is too high.Soundness uses the repair lemma; completeness controls sampling error with Kolmogorov’s and Chebyshev’s inequalities.Source: §4 · p. 19, §4.2 · p. 21

4.1 The Repair Lemma

  • The repair lemma bounds dist(w, Lℓ,r) by s(w) − 2m(w), where s(w) is the final height and m(w) the minimum prefix height.The construction first fixes negative prefixes, then reduces the final height to zero without creating a negative prefix.Source: §4.1 · pp. 19, 21

4.3 An optimal tester for the Dyck-1 language

  • D1 is exactly L1,1 restricted to words over {−1, 1}, so the excursion tester gives D1 an O(1/ε^2)-query tester.The reduction immediately rejects odd-length inputs and uses equality of the distances to D1 and L1,1 for even-length inputs.Source: §4.3 · p. 23

5 The optimality of our testers

The section proves that the testers’ dependence on ε is optimal. It establishes matching adaptive lower bounds for D1 and every fixed excursion language by reducing from a hard distribution-distinguishing problem.

5 The optimality of our testers

  • Ω(1/ε^2) queries are necessary for every two-sided-error adaptive ε-tester for D1 and for each fixed excursion language Lℓ,r.These lower bounds match the ε-dependence of the testers from Section 4.Source: §5 · p. 23, §5.1 · p. 24, §5.2 · p. 25

5.1 A lower bound for the Dyck-1 language

  • For D1, the lower bound encodes strings from two sum-conditioned distributions so that one maps to valid parentheses and the other to inputs ε-far from D1.Distinguishing the distributions requires Ω(1/γ^2) queries, with γ = 3ε.Source: §5.1 · pp. 24–25

5.2 A lower bound for all excursion languages

  • For every fixed Lℓ,r, a reduction using κ = min{ℓ, r} maps the hard distributions to valid or ε-far words, yielding the same Ω(1/ε^2) lower bound.The proof handles r ≥ ℓ and ℓ > r with symmetric choices of the sum-conditioned distribution.Source: §5.2 · p. 25

A Tail Bounds and Yao’s principle

The appendix records probability inequalities used in the tester analysis and states a version of Yao’s principle for property testing. The principle reduces randomized worst-case query lower bounds to distinguishing valid and far-input distributions.

A Tail Bounds and Yao’s principle

  • Kolmogorov’s inequality is included for independent mean-zero variables with finite variances, and Bernstein’s inequality is also listed among the tail bounds used in the tester proof.The section identifies these bounds as tools for the proof of Theorem 4.2.Source: A Tail Bounds and Yao’s principle · p. 28
  • Yao’s principle gives a route to a randomized query lower bound: exhibit distributions on valid and ε-far strings that deterministic q-query algorithms cannot distinguish.The far-input distribution must be supported on ε-far strings with probability 1 − o(1).Source: A Tail Bounds and Yao’s principle · p. 28
  • The appendix also describes conditioning on an event with equal probability under both distributions as a step in comparing their transcript distributions.The stated setup introduces BAD as such an event.Source: A Tail Bounds and Yao’s principle · p. 28

B Anti-concentration bounds

The appendix establishes anti-concentration bounds for sums of independent uniform and fair-coin variables. Its proof strategy splits uniform variables into coin and remainder components, then handles rare exceptional values by conditioning.

B Anti-concentration bounds

  • For independent fair-coin variables Yi, the probability that their sum equals any fixed t is at most 1/√s.The proof identifies the maximum point probability at a central value of the sum.Source: B Anti-concentration bounds · p. 29
  • For independent uniform Zi over {0, …, 2m − 1}, the probability that their sum equals any fixed t is at most 1/(m√s).The proof decomposes each Zi into a fair coin component and an independent uniform remainder.Source: B Anti-concentration bounds · pp. 29–30
  • For independent uniform Wi over {0, …, b}, the appendix proves a point-probability bound of less than 5/(b√s) for their sum when b ≥ 15.It conditions on the rare variables taking the exceptional value b and applies the preceding uniform-sum bound to the rest.Source: B Anti-concentration bounds · pp. 29–30

C Testability and relationships of subclasses of CFLs

This section places the paper’s results in the broader context of property testing for context-free languages. It points readers to an appendix hierarchy of linear languages and a survey of known complexity bounds.

C Testability and relationships of subclasses of CFLs

C.1 The Nondeterministic Biautomata Hierarchy

The section characterizes linear languages through nondeterministic biautomata and describes progressively restricted subclasses. Its hierarchy diagram uses arrows to denote language containment.

C.1 The Nondeterministic Biautomata Hierarchy

  • Nondeterministic biautomata read from both ends, and the languages they recognize are exactly the linear languages.Determinism yields a strict subclass containing the regular languages.Source: §C.1 · pp. 30–31
  • The hierarchy’s arrows indicate that the source language class is contained in the destination class.Source: Figure 4 · p. 31
  • The section presents increasingly restrictive subclasses through the types of grammars that generate their languages.DBW corresponds to deterministic linear grammars; DBWR to linear LL(1) grammars; and DBWP to Nasu–Honda deterministic linear languages.Source: §C.1 · p. 31
  • DBWP’s Nasu–Honda grammars require productions of the forms A → aBu or A → a and impose a uniqueness condition on matching production prefixes.Source: §C.1 · p. 31

C.2 Known query complexity bounds for subclasses of CFLs

Known testing bounds vary across formal-language classes: regular languages admit constant-query testing, while some context-free subclasses contain hard languages. The section surveys these bounds and notes that whether any context-free language requires more than √n queries remains open.

C.2 Known query complexity bounds for subclasses of CFLs

  • Regular languages have testers whose query complexity is independent of input length, whereas a context-free language requiring Ω(√n) queries shows this does not extend to all CFLs.Source: §C.2 · p. 31
  • The deterministic one-counter languages contain languages requiring Ω(log log n) queries, and the Dyck languages contain languages requiring Ω(n^2/5) queries.Source: §C.2 · p. 31
  • A linear language in DBWP requires Ω(n^2/5) queries, showing that even a highly restricted context-free subclass may contain a hard language.Source: §C.2 · pp. 31–32
  • Excursion languages provide a contrasting testable subclass: they are a natural generalization of D1 and are testable.Source: §C.2 · p. 32
  • Figure 5 collects known bounds and class containments; whether any CFL requires more than √n queries remains open.The figure also includes 3CNF properties, a non-context-free class requiring Ω(n) queries.Source: Figure 5 · p. 32, §C.2 · p. 32
Loading 2609.37431v1…