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.