将无限轨迹的义务性质转化为符号化自动机,实现高效合成。
Symbolic Synthesis for LTLf+ Obligations
- 基于前缀符号化DFA直接构建确定性弱自动机(DWA)
- 合成问题可在构造DWA后线性时间求解
- 适合形式化验证与自动化系统设计领域研究者
我们研究在LTLfp(LTLf对无限轨迹的扩展)中表达的义务性质的合成问题。义务性质是安全性和保证性(共安全性)性质的正布尔组合,属于Manna和Pnueli时序层次结构的第二层。尽管定义在无限轨迹上,这些性质仍保持了LTLf的大部分简洁性。我们证明它们可被转化为符号表示的确定性弱自动机(DWA),该转化直接由底层LTLf性质的符号化确定性有限自动机(DFA)获得。DWA继承了DFA的诸多算法优势,包括布尔封闭性和多项式时间最小化。此外,我们证明:一旦构建出DWA,义务性质的合成在理论上可在线性时间内完成。我们研究了多种用于求解相关DWA博弈的符号化算法,并通过实验评估其有效性。总体结果表明,LTLfp义务性质的合成可达到与LTLf合成几乎相同的效率。
原文摘要 · Abstract (English)
We study synthesis for obligation properties expressed in LTLfp, the extension of LTLf to infinite traces. Obligation properties are positive Boolean combinations of safety and guarantee (co-safety) properties and form the second level of the temporal hierarchy of Manna and Pnueli. Although obligation properties are expressed over infinite traces, they retain most of the simplicity of LTLf. In particular, we show that they admit a translation into symbolically represented deterministic weak automata (DWA) obtained directly from the symbolic deterministic finite automata (DFA) for the underlying LTLf properties on trace prefixes. DWA inherit many of the attractive algorithmic features of DFA, including Boolean closure and polynomial-time minimization. Moreover, we show that synthesis for LTLfp obligation properties is theoretically highly efficient - solvable in linear time once the DWA is constructed. We investigate several symbolic algorithms for solving DWA games that arise in the synthesis of obligation properties and evaluate their effectiveness experimentally. Overall, the results indicate that synthesis for LTLfp obligation properties can be performed with virtually the same effectiveness as LTLf synthesis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。