The Scope Grammar of Natural-Language Rules: Counting and Enumerating Readings modulo Logical Equivalence

Sherzod Turaev, Mary John

TL;DR

When translating natural-language rules into logic, a single sentence can have many valid bracketings (scope ambiguity), but many are logically identical. This paper provides a complete combinatorial theory for counting these distinct logical readings, proving that while the number of syntactic trees grows with the Catalan numbers (base 4), the number of logically unique readings grows much slower (base ~3.33), following the 3-Schröder sequence.

What Problem Does This Paper Address?

Natural language rules—like "Patients with hypertension and diabetes or kidney disease"—are inherently ambiguous. While an "autoformalizer" (like an LLM) might correctly identify the atoms (hypertension, etc.) and the connectives (and, or), it often leaves the scope unresolved.

Syntactically, a sequence of $n$ atoms and $k$ binary connectives can be bracketed in $C_k$ ways (the $k$-th Catalan number). For a rule with 10 atoms, that's 4,862 possible trees. However, due to laws like associativity (e.g., $(A \land B) \land C \equiv A \land (B \land C)$), many of these trees represent the exact same Boolean function.

The authors seek to bridge the gap between "how many ways can we parse this?" and "how many logically different rules could this actually mean?" This is critical for systems that need to expose ambiguity to human judges or certify rules for automated reasoning.

Methods

The authors investigate the scope grammar, a deliberately ambiguous context-free grammar where derivation trees represent possible readings. They focus primarily on the "positive fragment": rules that are repetition-free (each atom appears once) and negation-free.

Key techniques include:

  • Read-Once Normal Forms: They leverage the fact that positive read-once Boolean functions have a unique "normal form" tree (a cotree) where labels strictly alternate between $\land$ and $\lor$.
  • Dynamic Programming: They provide an $O(N^3)$ algorithm to enumerate reading classes by storing sets of Boolean functions realized over every possible span of the input string.
  • Combinatorial Recurrence: For the positive fragment, they derive an exact two-label recurrence to count unique readings based on the "operator word" (the sequence of $\land$ and $\lor$ symbols).
  • Generating Functions: They use analytic combinatorics to determine the growth rates and identify the sequences in the Online Encyclopedia of Integer Sequences (OEIS).

Datasets

The paper does not use traditional training datasets. Instead, it uses exhaustive enumeration for validation. The authors generated every possible bracketing and truth table for all operator patterns up to 11 atoms (and up to 16 for specific conjectures) to verify that their mathematical recurrences matched the ground-truth logical counts.

Key Insights and Ideas

  • The Ambiguity Criterion: A positive rule is logically ambiguous if and only if it contains both $\land$ and $\lor$. If a rule only uses one type of operator, all bracketings are equivalent due to associativity.
  • The "Boolean Quotient": The number of logically distinct readings is significantly smaller than the number of syntactic trees. As shown in Figure 1, the skeleton $a \land b \lor c \land d$ has 5 syntactic trees but only 4 logical classes.
Figure 1: The skeleton a ∧b ∨c ∧d has C3 = 5 derivation trees (top) but four reading classes (bottom): the third and fourth trees differ only in the association of the two conjunctions and contract to the same normal form, in which the root conjunction has three children. Gates are circled, conjunction in blue and disjunction in orange. The trees are authoritative; in the formula labels ∧binds more tightly than ∨, so a label such as (a ∧b ∨c) ∧d abbreviates ((a ∧b) ∨c) ∧d.
  • The Worst-Case Pattern: The "maximally alternating" pattern (e.g., $A \land B \lor C \land D \dots$) produces the most logical readings. The authors identified this sequence as the 3-Schröder numbers (OEIS A137842).
  • Growth Rates: While syntactic trees grow at a rate of $4^n$, the most ambiguous logical rules grow at a rate of $\approx 3.33^n$. This "gap" represents the exponential number of redundant readings that an autoformalizer can safely ignore.

Key Results

  • Exact Counting: The authors provide a table (Table 1) comparing the raw Catalan counts to the logical class counts. For $n=15$ atoms, there are over 2.6 million syntactic trees, but only ~312,000 logically distinct readings for the worst-case pattern.
Table 1: Reading classes of positive skeletons. The raw tree count is the Catalan number Cn−1; |R| depends only on the composition (Proposition 7.3). “alt.” is the maximally alternating pattern, “run” the single- operator pattern; the last column lists selected other compositions.
  • Complexity: Logical ambiguity for the positive fragment can be decided in a single $O(n)$ pass.
  • Lower Bound: The number of logical classes is at least $2^{\lfloor n/3 \rfloor}$ for any ambiguous positive skeleton.
  • Negation & Axioms: The paper extends the theory to handle negation and "hyponymy axioms" (e.g., knowing that "Emergency Room" is a type of "Hospital"), showing that while counting becomes harder, logical equivalence is still decidable via normal forms.

Limitations and Future Work

  • Negation Counting: While the authors can decide equivalence with negation, they haven't yet found a closed-form counting law like the one for the positive fragment. Negation is tricky because its scope can change the effective "operator word."
  • Maximality Conjecture: The authors verified that the alternating pattern is the worst case up to $n=15$, but a general proof for all $n$ remains an open problem (reduced to an "increment maximality" conjecture).
  • Background Axioms: The complexity of determining ambiguity when background knowledge is present (e.g., $A \implies B$) is likely higher and requires further study.

Summary updated

Abstract

A rule written for people fixes its atomic conditions and connectives but leaves open how the connectives are bracketed, and each bracketing is a different logical reading that an autoformalizer must resolve or expose. We study the scope grammar, a deliberately ambiguous context-free grammar whose derivation trees are the readings of a connective skeleton and whose quotient by logical equivalence is what matters downstream. A skeleton with $k$ binary connectives has $C_k$ derivation trees, the $k$-th Catalan number, but far fewer logically distinct readings. For the positive, repetition-free fragment we make the gap exact: through the uniqueness of the read-once normal form we characterize the realizable normal forms by lowest common ancestors and count them with a two-label recurrence over the operator word, verified against exhaustive enumeration up to eleven atoms. The count is invariant under reversal and $\wedge/\vee$ duality; a skeleton is ambiguous if and only if it uses both $\wedge$ and $\vee$, a one-pass test; and the number of classes is at least $2^{\lfloor n/3\rfloor}$. Up to fifteen atoms the alternating pattern is the worst case; its count has a cubic generating function, is the 3-Schröder sequence (OEIS A137842), and grows with base $\varphi^{5/2}\approx3.330$, below the Catalan base 4. We reduce maximality to an inequality on increments, verified to sixteen atoms, and explain why local exchange arguments cannot prove it. We also treat negation, exceptions, and background axioms, where normal-form uniqueness still decides equivalence but counting is open.
BibTeX
@misc{turaev2026scope,
  author = {Sherzod Turaev and Mary John},
  title = {{The Scope Grammar of Natural-Language Rules: Counting and Enumerating Readings modulo Logical Equivalence}},
  year = {2026},
  eprint = {2611.01825},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01825},
}
Figure