时间自动机的自动抽象算法
Automatic Abstraction Algorithm for Timed Automata
-
摘要: 为对付时间自动机规格分析验证中的状态爆炸问题,提出了一种自动抽象算法.它是直接在时间自动机 描述规格上而不是在规模大得多的语义模型上进行抽象,从而取得不大于时间自动机拓扑复杂性的四次方的多 项式复杂度.实验证明,该算法可应用于任何满足线性复位性质的时间自动机.此外,这种算法还可以用来简化 系统描述,提高其可理解性.Abstract: To deal with the state-explosion problem in the specification analysis and verification of timed automata, an automatic abstraction algorithm for timed automata was proposed. By directly abstracting the specifications of a timed automaton instead of its semantic model ofmuch bigger size, this algorithmyields a polynomial time complexity no more than the four power of its topology complexity. An experiment shows that the algorithm can be applied to any timed automaton satisfying a property called linear resetting and used to simplify system specifications to improve their understandability.
-
Key words:
- automatic /
- algorithm /
- timed automaton /
- abstraction
点击查看大图
计量
- 文章访问数: 1268
- HTML全文浏览量: 75
- PDF下载量: 176
- 被引次数: 0