The Scope Grammar of Natural-Language Rules: Counting and Enumerating Readings modulo Logical Equivalence
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 binary connectives has derivation trees, the -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 duality; a skeleton is ambiguous if and only if it uses both and , a one-pass test; and the number of classes is at least . 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 , 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
| alt. | run | selected compositions | ||
|---|---|---|---|---|
| 2 | 1 | 1 | 1 | |
| 3 | 2 | 2 | 1 | |
| 4 | 5 | 4 | 1 | |
| 5 | 14 | 10 | 1 | ; ; |
| 6 | 42 | 24 | 1 | ; ; ; ; |
| 7 | 132 | 66 | 1 |
Autoformalization
Autoformalization converts natural-language mathematics, proofs, and specifications into machine-checkable formal languages.
See all 124 papers