arXiv cs.CL· Sherzod Turaev, Mary John·· 11 小时前AI 评分18
自然语言规则的作用域语法：按逻辑等价计数与枚举读法
The Scope Grammar of Natural-Language Rules: Counting and Enumerating Readings modulo Logical Equivalence
AI 导读
研究将人类规则自动形式化时连接词括号方式产生的不同逻辑读法：含 k 个二元连接词的骨架有第 k 个 Catalan 数棵推导树，但逻辑上不同的读法远少于此。针对正向、无重复片段，作者用 read-once 范式唯一性刻画可实现范式，并以双标签递推计数，经至多 11 个原子的穷举验证。
正文 · AI 翻译
摘要：为人类书写的规则固定了其原子条件和连接词，但未规定连接词如何加括号，而每种括号方式都是一种不同的逻辑解读，自动形式化器必须解决或揭示它。我们研究作用域文法，这是一种刻意歧义的上下文无关文法，其推导树是连接词骨架的解读，而其按逻辑等价取商后的结果才是下游所关心的。一个含 $k$ 个二元连接词的骨架有 $C_k$ 棵推导树，即第 $k$ 个卡塔兰数，但逻辑上不同的解读要少得多。对于正、无重复片段，我们使这一差距精确化：通过读一次范式（read-once normal form）的唯一性，我们用最低公共祖先刻画可实现范式，并用算子词上的双标签递推对其计数，经穷举枚举验证至十一个原子。该计数在反转和 $\wedge/\vee$ 对偶下不变；一个骨架是歧义的当且仅当它同时使用 $\wedge$ 和 $\vee$，这是一次性检验；且等价类数目至少为 $2^{\lfloor n/3\rfloor}$。至十五个原子，交替模式是最坏情况；其计数具有三次生成函数，是 3-Schröder 序列（OEIS A137842），并以底 $\varphi^{5/2}\approx3.330$ 增长，低于卡塔兰底 4。我们将极大性归约为关于增量的不等式，验证至十六个原子，并解释为何局部交换论证无法证明它。我们还处理否定、例外和背景公理，其中范式唯一性仍能判定等价，但计数问题仍未解决。
| 评论： | 13 页，1 幅图，1 张表 |
| 主题： | 形式语言与自动机理论（cs.FL）；计算与语言（cs.CL）；计算机科学中的逻辑（cs.LO） |
| MSC 分类： | 68Q42, 05A15, 68Q45, 03B05 |
| ACM 分类： | F.4.2; F.4.3; G.2.1 |
| 引用为： | arXiv:2611.01825 [cs.FL] |
| （或本版本使用 arXiv:2611.01825v1 [cs.FL]） | |
| https://doi.org/10.48550/arXiv.2611.01825 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Sherzod Turaev [查看电子邮件]
[v1]
2026 年 11 月 1 日星期日 11:45:13 UTC（55 KB）
来源：arXiv cs.CL · arxiv.org