Bounded choice-free Petri net synthesis: algorithmic issues
Bounded choice-free Petri net synthesis: algorithmic issues
复制标题
DOI：
10.1007/s00236-017-0310-9
复制
发表时间：
2018-11-01
期刊：
影响因子：
0.6
通讯作者：
Schlachter, Uli
中科院分区：
文献类型：
--
作者：
Best, Eike;Devillers, Raymond;Schlachter, Uli
本文描述了一个合成程序，致力于从有限持久过渡系统中构建无选择Petri网，只要可能。利用无选择Petri网的特性，提出了一种两步法。预合成步骤检查转换系统的必要结构属性，并构造第二步所需的一些数据结构。然后，从一般的区域理论方法中提取出线性不等式的简化系统的最小化集。这导致必须解决线性不等式的状态集的实质性缩小，并允许早期检测故障，由建设性的错误信息支持。对所得算法的性能进行了测量，并与现有的合成工具进行了数值比较。
This paper describes a synthesis procedure dedicated to the construction of choice-free Petri nets from finite persistent transition systems, whenever possible. Taking advantage of the properties of choice-free Petri nets, a two-step approach is proposed. A pre-synthesis step checks necessary structural properties of the transition system and constructs some data structures needed for the second step. Then, a minimised set of simplified systems of linear inequalities is distilled from a general region-theoretic approach. This leads to a substantial narrowing of the sets of states for which linear inequalities must be solved, and allows an early detection of failures, supported by constructive error messages. The performance of the resulting algorithm is measured and compared numerically with existing synthesis tools.