💻 computer science

The Temporal Logic Synthesis Format TLSF v1.2

本文介绍了时序逻辑综合格式（TLSF）v1.2 的扩展，该版本在标准 LTL 基础上增加了集合、函数及参数等高阶构造，并引入了新算子及针对有限执行的 LTLf 语义选项。

原作者： Swen Jacobs, Guillermo A. Perez, Philipp Schlehuber-Caissier

发布于 2026-04-15

📖 1 分钟阅读☕ 轻松阅读

原作者： Swen Jacobs, Guillermo A. Perez, Philipp Schlehuber-Caissier

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一种名为 TLSF v1.2 的新格式，你可以把它想象成是给“自动机器人设计师”写的一份超级详细的说明书。

在计算机科学里，我们想造出能自动控制交通灯、自动驾驶汽车或者工厂流水线的“智能大脑”。以前，我们写说明书（规范）时，只能描述“如果发生 A，就执行 B"这种简单的逻辑。但现实世界很复杂，有时候任务是有终点的（比如“把货物送到仓库就停止”），有时候我们需要定义一整类相似的任务（比如“不管仓库有 10 个还是 100 个格子，规则都一样”）。

TLSF v1.2 就是为了解决这些新问题而升级的“说明书语言”。

下面我用几个生活中的比喻来解释它的核心升级：

1. 从“无限循环”到“有始有终” (LTLf 的引入)

旧版本 (LTL)：就像你在教一个机器人“永远保持房间整洁”。只要你在，它就得一直干活，没有下班的时候。
新版本 (LTLf)：就像你教机器人“把房间打扫干净然后去睡觉”。这里有一个明确的终点。
- 比喻：以前的指令是“一直跑”，现在的指令是“跑 10 圈，然后停下”。
- 新工具：为了区分“明天继续”和“明天必须存在”，它引入了一个强力的“下一步”按钮（ $X[!]$ $X [!]$ ）。
  - 普通的“下一步” ( $X$ )：如果游戏结束了，它就说“没关系，反正没下一步了”。
  - 强力的“下一步” ( $X[!]$ )：如果游戏结束了，它就说“不行！你必须还有下一步才能满足条件！”这就像在说“如果你还没到终点，就不能算赢”。

2. 给说明书加上了“变量”和“模板” (参数化)

旧版本：如果你要描述 10 个不同的红绿灯，你得写 10 份说明书。
新版本：你可以写一份模板，里面写上“假设有 $N$ $N$ 个路口”。
- 比喻：以前是手抄 10 份菜单，现在是用 Excel 表格，只要改一下“人数”这一栏，菜单自动就生成 10 份不同的了。这让设计师能一次性定义一大类问题，而不是重复劳动。

3. 引入“信号总线”和“枚举” (更聪明的信号管理)

旧版本：每个开关都要单独命名，比如“开关 1"、“开关 2"……如果有一排 100 个灯，名字就写疯了。
新版本：
- 总线 (Bus)：就像把 100 个开关打包成一个“灯条”。你可以直接说“灯条的第 5 个灯亮了”，而不需要给每个灯起名字。
- 枚举 (Enumeration)：就像给状态起别名。比如把"001"定义为“左转”，"010"定义为“直行”。写说明书时直接写“如果是左转”，机器人才懂这代表"001"。这让说明书读起来像人类语言，而不是乱码。

4. 像写代码一样写逻辑 (函数和宏)

新功能：你可以定义函数。
- 比喻：以前你想说“如果 A 且 B，则 C"，每次都要写一遍。现在你可以定义一个叫 如果_且_则 的函数。以后只要写 如果_且_则(A, B, C)，机器就自动展开成复杂的逻辑。
- 模式匹配：这就像是一个“找茬”游戏。你可以写一个规则：“如果你看到‘直到’( $U$ ) 这个逻辑词，就只取它前面的部分；如果是别的，就取它的下一步。”这让处理复杂逻辑变得非常灵活。

5. 两种“世界观” (语义模式)

论文还提到了两种看待世界的方式：

标准模式：假设世界是无限的，只要一直运行下去，规则就要一直满足。
有限模式 (Finite)：假设世界是有尽头的（比如任务完成就结束）。在这种模式下，规则必须在“结束”的那一刻之前满足。
- 比喻：
  - 标准模式：像“马拉松”，只要你在跑，姿势就要对。
  - 有限模式：像“短跑冲刺”，你必须在冲过终点线的那一瞬间，姿势是对的，而且冲过线后你就停下来了。

总结

这篇论文其实是在说：“我们要让给机器人写的说明书变得更聪明、更灵活、更像人类语言。”

它不再只是死板的逻辑代码，而是加入了：

明确的终点（任务做完就停）。
万能模板（一套规则管所有规模）。
打包信号（像操作数组一样操作开关）。
自定义函数（把复杂逻辑封装成简单的词）。

有了这个新格式（TLSF v1.2），工程师们就能更容易地设计出能处理复杂、有终点任务的自动化系统了。就像是从“手写单行代码”进化到了“使用现代编程语言”一样。

这是一份关于 TLSF v1.2 (Temporal Logic Synthesis Format v1.2) 的技术总结。该文档由 Swen Jacobs、Guillermo A. Pérez 和 Philipp Schlehuber-Caissier 撰写，旨在扩展现有的时序逻辑综合格式（TLSF），以支持更复杂的规范描述和基于有限执行（LTLf）的合成问题。

以下是详细的技术总结：

1. 问题背景 (Problem)

现有的 TLSF v1.1 格式基于标准的线性时序逻辑（LTL），虽然支持集合、函数和参数化等高级构造，但在处理**有限执行（Finite Executions）**场景时存在局限性。

LTL 的局限性：标准 LTL 通常定义在无限序列上，而许多实际系统（如任务完成型系统、协议终止场景）的行为是有限长的。
语法与语义缺失：之前的版本缺乏对 LTLf（有限字上的 LTL）语法的直接支持，特别是缺乏区分“强下一时刻”（Strong Next）和“弱下一时刻”（Weak Next）的机制，这在有限序列的边界条件处理上至关重要。
工具链需求：需要一种标准化的格式来定义参数化问题族，并支持从无限语义到有限语义的转换，以便合成工具（如 SYNTCOMP）能够处理终止控制器（Terminating Controllers）。

2. 方法论 (Methodology)

本文提出了一种扩展的 TLSF v1.2 格式，通过以下核心方法论进行改进：

A. 引入 LTLf 语义与强下一时刻算子

语法扩展：在基础 LTL 表达式中增加了 X[!]（强下一时刻）算子。
- X ϕ (弱下一时刻)：在序列末尾评估时自动为真（因为不存在下一个状态，所以不违反）。
- X[!] ϕ (强下一时刻)：要求序列必须存在下一个状态且该状态满足 ϕ。
语义定义：明确了 LTLf 在有限字 $\alpha = a_0...a_{n-1}$ 上的归纳定义。特别强调了终止条件：控制器通过输出一个特殊的 alive 信号（或 as 信号）来指示序列终止。当 alive 信号为假时，表示序列结束。

B. 终止控制器模型 (Terminating Controllers)

定义了两种终止控制器模型，用于合成满足 LTLf 规范的实现：

终止 Mealy 机：输出依赖于当前状态和输入。机器在达到终止状态时停止，且终止状态不输出 alive 信号。
终止 Moore 机：输出仅依赖于当前状态。

关键机制：引入了 alive 信号作为输出命题。如果当前状态不是终止状态，alive 必须为真；如果是终止状态，alive 为假。这允许控制器明确声明“任务已完成”。

C. 格式扩展 (Full Format)

在原有的 INFO 和 MAIN 部分基础上，增加了 GLOBAL 部分，支持更复杂的规范描述：

参数化 (PARAMETERS)：允许定义数值参数，用于生成问题族。
定义 (DEFINITIONS)：支持定义枚举类型（Enumerations）、函数（Functions）和宏。
- 枚举：用于定义信号总线（Bus）的特定值模式（如 LEFT, RIGHT），并自动施加约束。
- 函数：支持递归函数和模式匹配（Pattern Matching），允许根据 LTL 公式的结构动态生成子公式。
大算子符号 (Big Operators)：引入 $\Sigma, \Pi, \cup, \cap$ 等符号的语法糖（如 &&[i IN S]），简化参数化公式的书写。

D. 语义变体

支持六种语义变体，结合了目标模型（Mealy/Moore）和逻辑语义（标准/严格/有限）：

标准语义：标准的 LTL 蕴含关系。
严格语义 (Strict)：使用严格蕴含（Strict Implication），常用于 GR(1) 规范合成。
有限语义 (Finite)：将上述逻辑映射到 LTLf 语义上，处理有限执行。

3. 关键贡献 (Key Contributions)

TLSF v1.2 规范发布：正式定义了支持 LTLf 的扩展格式，填补了标准 LTL 格式在有限执行合成领域的空白。
强/弱下一时刻算子区分：在语法层面明确区分 X 和 X[!]，解决了有限序列边界条件的歧义问题。
终止控制器形式化：详细定义了基于 alive 信号的终止 Mealy/Moore 机模型，并给出了其语言（Language）和约简语言（Reduced Language）的数学定义。
高级抽象机制：
- 通过 GLOBAL 部分引入参数化、枚举和函数，使得单个规范文件可以描述整个参数化的问题族。
- 引入模式匹配函数，允许对 LTL 公式进行结构化的变换和宏定义。
工具链更新：更新了 Synthesis Format Conversion Tool (SyFCo)，支持输出 ltlxba-fin 格式，使其能与 Spot 等工具兼容，直接服务于 LTLf 合成竞赛（SYNTCOMP）。

4. 结果与示例 (Results & Examples)

语法示例：
- 定义了 X[!] 算子，例如 G(i1 <-> o1) ^ (o2 || X[!]true) 表示在序列结束前必须满足某些条件，且序列必须在满足 o2 或显式终止时结束。
- 展示了如何使用枚举定义信号总线约束（如 Position 枚举限制总线宽度）。
语义示例：
- 通过图 1 和图 2 展示了满足特定 LTLf 公式的终止 Mealy 机和 Moore 机。
- 证明了在 Moore 语义下，某些依赖输入的公式不可实现，需修改为依赖状态的公式（如 G(i1 <-> X(o1))）。
兼容性：新格式向后兼容 TLSF v1.1 的旧标识符（如 INVARIANTS 等），并支持 C 风格注释。

5. 意义 (Significance)

理论价值：为有限执行系统的形式化验证和合成提供了统一且严谨的语法与语义基础，特别是解决了“何时停止”这一在无限 LTL 中不直观但在实际系统中至关重要的问题。
工程实践：
- 使得合成工具能够处理任务导向型系统（Task-oriented systems），这些系统在完成特定任务后自然终止，而不是无限运行。
- 通过参数化和函数支持，极大地提高了规范编写的效率和复用性，减少了为不同规模系统编写重复规范的工作量。
社区影响：作为 SYNTCOMP 等合成竞赛的标准格式更新，推动了 LTLf 合成算法的研究和工具开发，促进了学术界和工业界在有限执行系统合成方面的合作。

总结：TLSF v1.2 不仅是一个格式更新，更是将时序逻辑合成从“无限运行”扩展到“有限任务完成”的关键桥梁，通过引入强下一时刻算子、终止控制器模型和高级参数化机制，显著提升了规范表达的能力和合成问题的实用性。