Reachability Set Generation Using Hybrid Relation Compatible Saturation
Reachability Set Generation Using Hybrid Relation Compatible Saturation
复制标题
使用混合关系兼容饱和度生成可达性集
DOI：
10.1007/978-3-030-61739-4_3
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Miner, Andrew S
中科院分区：
文献类型：
--
作者：
Biswal, Shruti;Miner, Andrew S
使用饱和等符号算法生成任何有限离散状态系统的状态空间需要使用决策图或兼容结构来编码其可达集和转移关系。对于可以使用普通Petri网（PN）形式化表示的系统，隐式关系，一种基于决策树的转移关系表示的静态替代方案，可以显着提高饱和性能。然而，在实践中，一些系统需要更一般的模型，如自修改Petri网，目前不能利用隐式关系，因此使用决策图，反复重建，以适应不断变化的系统变量的边界，潜在地导致饱和算法的开销。这项工作引入了一种混合表示的过渡关系，结合决策图和隐式关系，以减少重建开销的饱和算法的一般类的模型。在不同工具的几个基准模型上的实验证明了这种表示的效率。
Generating the state space of any finite discrete-state system using symbolic algorithms like saturation requires the use of decision diagrams or compatible structures for encoding its reachability set and transition relations. For systems that can be formally expressed using ordinary Petri Nets (PN), implicit relations, a static alternative to decision diagram-based representation of transition relations, can significantly improve the performance of saturation. However, in practice, some systems require more general models, such as self-modifying Petri nets, which cannot currently utilize implicit relations and thus use decision diagrams that are repeatedly rebuilt to accommodate the changing bounds of the system variables, potentially leading to overhead in saturation algorithm. This work introduces a hybrid representation for transition relations, that combines decision diagrams and implicit relations, to reduce the rebuilding overheads of the saturation algorithm for a general class of models. Experiments on several benchmark models across different tools demonstrate the efficiency of this representation.
登录
查看更多内容
使用可扩展决策图生成异步系统的符号状态空间
DOI：
10.1007/978-3-540-95891-8_52
发表时间：
2009
期刊：
2010 Seventh International Conference on the Quantitative Evaluation of Systems
影响因子：
--
作者：
Min Wan;Gianfranco Ciardo
通讯作者：
Gianfranco Ciardo
DOI：
10.1007/978-3-319-57861-3_14
发表时间：
2017-06
期刊：
--
影响因子：
--
作者：
Kristóf Marussy;V. Molnár;András Vörös;I. Majzik
通讯作者：
Kristóf Marussy;V. Molnár;András Vörös;I. Majzik
饱和度无限制
DOI：
10.1007/3-540-36577-x_27
发表时间：
2003
期刊：
Design, Automation and Test in Europe Conference and Exhibition, 1999. Proceedings (Cat. No. PR00078)
影响因子：
--
作者：
Gianfranco Ciardo;Robert M. Marmorstein;Radu I. Siminiceanu
通讯作者：
Radu I. Siminiceanu
DOI：
10.1007/11562436_32
发表时间：
2005
期刊：
Design, Automation and Test in Europe Conference and Exhibition, 1999. Proceedings (Cat. No. PR00078)
影响因子：
--
作者：
J. Couvreur;Y. Thierry
通讯作者：
Y. Thierry
DOI：
10.1007/978-3-030-21571-2_17
发表时间：
2019
期刊：
International Conference on Applications and Theory of Petri Nets and Concurrency
影响因子：
--
作者：
Biswal, Shruti;Miner, Andrew
通讯作者：
Miner, Andrew