arXiv:2509.06262cs.FLcs.AI2025-09被引 1

从正负样本中自动合成最简时序正则表达式,用于描述系统实时行为。

On Synthesis of Timed Regular Expressions

  • 通过枚举与剪枝生成候选参数化时序正则表达式
  • 将一致性验证转化为SMT公式求解,得到最优时间约束
  • 适用于需要精确时序建模的工业级系统设计场景

时序正则表达式是描述网络物理系统实时行为的形式化工具。本文研究时序正则表达式的合成问题,目标是从给定的正负样本中生成一个一致的时序正则表达式,即接受所有正例、拒绝所有负例。首先通过分析简单时序正则表达式证明了该问题的可判定性。随后提出一种生成最小长度一致表达式的两阶段方法:第一阶段枚举并剪枝候选的参数化时序正则表达式;第二阶段将一致性要求编码为满足性模理论(SMT)公式,并求解以获得参数时间约束的解。最后在随机生成的目标时序模型行为及一个案例研究上评估了所提方法的有效性。

原文摘要 · Abstract (English)

Timed regular expressions serve as a formalism for specifying real-time behaviors of Cyber-Physical Systems. In this paper, we consider the synthesis of timed regular expressions, focusing on generating a timed regular expression consistent with a given set of system behaviors including positive and negative examples, i.e., accepting all positive examples and rejecting all negative examples. We first prove the decidability of the synthesis problem through an exploration of simple timed regular expressions. Subsequently, we propose our method of generating a consistent timed regular expression with minimal length, which unfolds in two steps. The first step is to enumerate and prune candidate parametric timed regular expressions. In the second step, we encode the requirement that a candidate generated by the first step is consistent with the given set into a Satisfiability Modulo Theories (SMT) formula, which is consequently solved to determine a solution to parametric time constraints. Finally, we evaluate our approach on benchmarks, including randomly generated behaviors from target timed models and a case study.

时序逻辑形式化验证SMT求解系统合成

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。