...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Pomiary Automatyka Kontrola >Wielomianowy algorytm wyznaczania hipergrafu współbieżności w sieciach Petriego swobodnego wyboru
【24h】

Wielomianowy algorytm wyznaczania hipergrafu współbieżności w sieciach Petriego swobodnego wyboru

机译：确定自由Petri网中并发超图的多项式算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the paper a new algorithm of concurrency hypergraph computation is presented. The main aim of the proposed method is computation of a concurrency hypergraph in the polynomial time. The algorithm input is specified by the Petri net that belongs to the Free Choice subclass. Based on the net structure, the method outputs the concurrency relations between all places in the net. Particular relations are stored by the concurrency hypergraph instead of the concurrency graph, which is currently practiced. The hypergraph permits to store information about relations between all places in the net. In case of the concurrency graph it is limited to relations between pairs of places. Therefore, application of the concurrency hypergraph seems to be more intuitive and natural. The algorithm bases on the traditional solutions, however particular concurrency relation may contain more than two places which is not possible in currently known methods. The proposed solution is especially valuable in combination with the method presented in [1, 2] and permits to find the subsequent SM-Components in the polynomial time. The algorithm was experimentally verified. The method was compared with the traditional solution, where all maximal cliques in the concurrency graph were computed. The obtained results proved very high effectiveness of the proposed algorithm, which was always better than methods based on the graph theory. We have also noticed that the effectiveness increases drastically with the number of places and transitions in the Petri net.%W referacie zaproponowano metodę umożliwiającą określenie strukturalnej relacji współbieżności w sieciach Petriego swobodnego wyboru (Free Choice). Algorytm znajduje miejsca wzajemnie współbieżne na podstawie struktury sieci oraz miejsc oznaczonych markerem startowym. W odróżnieniu od istniejących algorytmów, proponowana metoda znajduje wszystkie miejsca wzajemnie współbieżne, wyznaczając hipergraf współbieżności. Przeprowadzone badania eksperymentalne potwierdzają bardzo wysoką skuteczność proponowanej metody.
机译：本文提出了一种新的并发超图计算算法。该方法的主要目的是在多项式时间内计算并发超图。算法输入由属于“自由选择”子类的Petri网指定。该方法基于网络结构，输出网络中所有位置之间的并发关系。特殊关系由并发超图存储，而不是由当前实践的并发图存储。超图允许存储有关网络中所有位置之间的关系的信息。在并发图的情况下，它仅限于成对的场所之间的关系。因此，并发超图的应用似乎更加直观自然。该算法基于传统解决方案，但是特定的并发关系可能包含两个以上的位置，这在当前已知的方法中是不可能的。所提出的解决方案与[1，2]中提出的方法结合起来特别有价值，并允许在多项式时间内找到后续的SM分量。该算法已通过实验验证。该方法与传统解决方案进行了比较，在传统解决方案中，计算了并发图中的所有最大集团。所获得的结果证明了所提算法的有效性，始终优于基于图论的方法。我们还注意到，效率随着陪替氏网络中的位置和过渡次数而急剧增加。 Algorytm znajduje miejsca wzajemniewspółbieżnena podstawie struktury sieci oraz miejsc oznaczonych markerem startowym。 Wodróżnieniuodistniejących阿尔及利亚，proponowana metoda znajduje wszystkie miejsca wzajemniewspółbieżne，wyznaczająchipergrafwspółbieżności。 Przeprowadzone badania eksperymentalnepotwierdzająbardzowysokąskutecznośćproponowanej旋律。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号