权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Algorithms for Synthesis and Pre-Synthesis Based on Petri Net Structure Theory (ASYST)

基于Petri网结构理论的合成和预合成算法（ASYST）

基本信息

批准号：
336738132
负责人：
Professor Dr. Ernst-Rüdiger Olderog, since 11/2018
金额：
--
依托单位：
Abteilung Entwicklung korrekter Systeme
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2017
资助国家：
德国
起止时间：
2016-12-31 至 2021-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/336738132?language=en
关键词：
Algorithms Synthesis Pre Based Petri

项目摘要

This project contributes to the theory of synthesising Petri nets from labelled transition systems, the basic concepts and algorithms underlying which have recently been described in a monography entitled Petri Net Synthesis (Springer-Verlag, 2015), by Badouel, Bernardinello, and Darondeau. Petri net synthesis is an actively researched, as well as a highly application-prone, topic. Probably, the most well-known areas of application are Asynchronous Digital Design and Process Mining. In both areas, the focus is on special Petri nets (choice-free nets, and marked graphs). For reasons such as this, it is important to optimise Petri net synthesis towards special classes of systems. Optimising with respect to various other classes of Petri nets is vital in order to pave the way for diverse other types of application.A general Petri net synthesis algorithm would involve solving a large number of linear-algebraic inequation systems. If solutions exist, then they can be used in order to construct so-called regions (that is, suitable structures relating to a given transition system). Targetting this algorithm towards specific system classes requires, in general, adding more linear inequation systems, which may slow down the synthesis. The aim of the present project is to demonstrate how established knowledge about the structural characteristics of the target classes can be used in order to offset the slow-down effect, and preferably, lead to better algorithms. It was already shown that, for marked graphs, there exists an algorithm by which only unavoidable regions are constructed very efficiently. In order to corroborate our aim for other Petri net classes as well, we shall investigate ways in which target class specific structural properties can be used in order to reduce the number of region constructions. A general method of incorporating such properties is to provide an explicit pre-synthesis stage during which they can be checked on a given input. The project aims -- inspired by a published, extensive, feasibility study for choice-free systems -- at proving that knowing structural properties before synthesis leads to a reduction of the amount of region construction and to a corresponding optimisation of synthesis.

该项目有助于从标记转换系统合成Petri网的理论，其基本概念和算法最近在Badouel， Bernardinello和Darondeau的题为Petri网合成的专著（Springer-Verlag, 2015）中进行了描述。Petri网合成是一个研究活跃、应用前景广阔的课题。也许，最著名的应用领域是异步数字设计和过程挖掘。在这两个领域，重点是特殊的Petri网（无选择网和标记图）。由于这样的原因，对特殊类型的系统优化Petri网综合是很重要的。为了为各种其他类型的应用铺平道路，对各种其他类型的Petri网进行优化至关重要。一般的Petri网综合算法需要求解大量的线性代数不等式系统。如果存在解决方案，则可以使用它们来构建所谓的区域（即与给定转换系统相关的适当结构）。一般来说，针对特定系统类的算法需要添加更多的线性不等式系统，这可能会减慢综合速度。本项目的目的是演示如何使用关于目标类的结构特征的既定知识来抵消减速效应，并优选地导致更好的算法。前面已经证明，对于有标记的图，存在一种算法，可以非常有效地只构造不可避免的区域。为了证实我们对其他Petri网类的目标，我们将研究使用目标类特定结构属性以减少区域构建数量的方法。整合这些属性的一般方法是提供一个明确的预合成阶段，在此期间可以对给定的输入进行检查。该项目的灵感来自于一项已发表的、广泛的、无选择系统的可行性研究，旨在证明在合成之前了解结构特性可以减少区域构建的数量，并相应优化合成。