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

该项目有助于从标记的变迁系统合成Petri网的理论，其基本概念和算法最近在Badouel，Bernardinello和Darondeau的题为Petri网合成的专著中进行了描述（Springer-Verlag，2015）。Petri网综合是一个非常活跃的研究领域，也是一个非常有应用前景的课题。最著名的应用领域可能是异步数字设计和流程挖掘。在这两个领域中，重点是特殊的Petri网（无选择网和标记图）。由于这样的原因，重要的是优化Petri网合成到特殊类别的系统。为了给其他各种类型的应用铺平道路，对其他各种类型的Petri网进行优化是至关重要的。一般的Petri网综合算法需要求解大量的线性代数不等式系统。如果存在解决方案，那么它们可以用来构建所谓的区域（即与给定的过渡系统相关的适当结构）。将该算法针对特定的系统类需要，在一般情况下，添加更多的线性不等式系统，这可能会减慢合成。本项目的目的是展示如何建立知识的结构特征的目标类可以使用，以抵消减速效应，并优选地，导致更好的算法。它已经表明，对于标记图，存在一个算法，只有不可避免的地区是非常有效地构建。为了证实我们对其他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.