cs.FLNov 1, 2026

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

Authors: Sherzod Turaev

Organizations: Department of Computer Science and Software Engineering College of Computing and Artificial Intelligence United Arab Emirates University, Al Ain, United Arab Emirates

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 kk binary connectives has CkC_k derivation trees, the kk-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⌊n/3⌋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 φ5/2≈3.330\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.

Figures & tables

Explore similar work

CardsList
  1. On Counting Graphs for Modal Logic with Counting

    Oct 19, 2026Avijeet Ghosh, François SchwarzentruberGNN Expressivity

  2. Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding

    Mar 4, 2026Faruk Alpay, Bilge SenturkGrammar-Constrained Decoding

  3. From Statute to Control Flow: Span-Grounded Deontic Trees for Defeasible Scope Parsing

    Jun 8, 2026Jian Chen, Siyuan Li, Chucheng Wan +1Logical ReasoningLegal NLP