符号导数:理论模下的正则性与?-正则性

《Journal of the ACM》:Symbolic Derivatives: Regularity and ?-Regularity Modulo Theories

【字体: 大 中 小 】 时间:2026年09月23日 来源:Journal of the ACM 3.0

编辑推荐:

   # 摘要 符号导数支持在基于词(words)的逻辑(如扩展正则表达式)中,将公式懒惰地(lazy)展开为符号自动机。符号自动机是支持潜在无限字母表(如有理数集)的有限状态自动机,通常应用于有限词上的正则表达式和语言。在符号自动机(或称模 A 的自动机)中,字母表由一个有效的

  

# 摘要

符号导数支持在基于词(words)的逻辑(如扩展正则表达式)中,将公式懒惰地(lazy)展开为符号自动机。符号自动机是支持潜在无限字母表(如有理数集)的有限状态自动机,通常应用于有限词上的正则表达式和语言。在符号自动机(或称模 A 的自动机)中,字母表由一个有效的布尔代数 A 表示,并由一个可满足性判定过程来支撑。无限词上的正则语言(即所谓的 ω-正则语言)拥有一段与有限词上的正则语言并行的丰富历史,并且通过 Büchi 自动机和时序逻辑,在模型检测方面有已知的重要应用。我们通过迁移项(transition terms)将符号导数和自动机推广到支持 ω-正则语言,将多种经典自动机和逻辑统一到一个框架中,该框架提供了支持模 A 符号模型检测所需的全部要素。具体而言,我们定义了:(1)模 A 的交替 Büchi 自动机(ABWA)和(非交替的)非确定性 Büchi 自动机(NBWA);(2)一个交替消除算法,该算法增量地从 ABWA 构造出 NBWA,并且也用于构造两个 NBWA 的乘积;(3)一个模 A 的线性时序逻辑 LTL?A? 的定义,该定义推广了 Vardi 从 LTL 构造交替 Büchi 自动机的方法,利用(2)通过 ABWA 从模 A 的 LTL 转换到 NBWA。最后,我们提出了 RLTL?A?,它是 LTL?A? 与模 A 扩展正则表达式的结合,推广了属性规范语言(PSL)。我们的结合方案支持正则表达式求补,这是 PSL 不支持的,但可以通过使用迁移项自然地实现。我们使用 Lean 证明助手形式化了 RLTL?A? 的语义,并形式化地建立了主要推导定理的正确性。

---

# AI 摘要

**AI 生成的摘要(实验性)**

本摘要由自动化工具生成,未经论文作者撰写或审核。本摘要旨在辅助文献发现,帮助读者评估相关性,并帮助相邻研究领域的读者理解本文工作。本摘要旨在补充作者提供的摘要,后者仍是论文的主要摘要。全文仍是权威版本的记录。[点击此处了解更多](#)。[点击此处对该摘要的准确性、清晰度和实用性进行评论](#)。这样做将有助于改进未来重新生成的版本。

**AI 生成摘要**

由基于已发表文章文本的自动系统生成。版本创建于 2026 年 9 月 22 日。

本文提出了一个全面的符号导数框架,该框架能够将基于词(words)的逻辑中的公式懒惰地展开为符号自动机。该工作将符号自动机扩展到处理潜在无限字母表,通过有效的布尔代数与可满足性判定过程的配对来表示字母表,从而允许高效推理而不需要指数级的命题编码。

核心技术创新是引入了迁移项(transition terms),即以字母表谓词和语言叶节点为参数的嵌套 if-then-else 表达式。这些迁移项作为不同逻辑中符号导数的统一表示,并通过可满足性检查移除不可达子项来实现增量简化。该框架包含两个主要域:用于表示迁移条件的字母表 EBA 和用于表示目标状态或公式的叶节点 EBA。

作者将经典的无限词上的 ω-正则语言推广到模背景理论的形式,将有限自动机理论中的基本概念提升到了更高阶。他们定义了模理论的交替 Büchi 自动机,并开发了一种交替消除算法,该算法构造等价的非确定性自动机同时避免了最小项化。该算法通过在构造过程中始终利用背景理论中的可满足性检查来实现显著的效率提升。

线性时序逻辑通过符号导数扩展到模理论的形式,在展开为自动机时保持语义结构。一个关键进展是将 LTL 与扩展正则表达式结合成一种统一的逻辑,称为 RLTL,其中融合了 ω-融合和弱闭包算子。这种结合通过懒惰传播否定来自然支持正则表达式求补,而采用需要确定化的其他方法则难以实现。

本文通过云服务跟踪分析展示了实际应用性,其中动作表示为 JSON 值,属性必须同时表达时序模式和数据约束。通过将 SMT 推理与时序逻辑深度集成,该框架避免了指数级命题编码同时保持了对标准理论的可判定性。

形式化的 Lean 证明建立了 RLTL 核心基于导数的算法的正确性,为理论提供了高度信心。该框架表明,RLTL 在可判定理论上精确捕获了模这些理论的 ω-正则性,并通过扩展到 Rabin 自动机,能够针对某些正则类补运算否定的 ω-闭包。

本文工作将几种经典的自动机和逻辑构造统一在一个代数上自洽的框架中。通过导数和迁移项保持语义结构,该方法能够启用状态缩减和蕴含等优化,而这些优化在经典自动机构造中会丢失。本文讨论了未来工作,包括额外定理的形式验证、与验证工具的集成,以及向更丰富的逻辑和时序算子的可能扩展。

本内容为 AI 生成。[了解更多](#)
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号