Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis

Issue title: Application and Theory of Petri Nets and Concurrency 2019

Guest editors: Susanna Donatelli, Stefan Haar and Slawomir Lasota

Article type: Research Article

Authors: Devillers, Raymond^{; *}

Affiliations: Département d’Informatique, Université Libre de Bruxelles, Boulevard du Triomphe, C.P. 212, B-1050 Bruxelles, Belgium. rdevil@ulb.ac.be

Correspondence: [*] Address for correspondence: Département d’Informatique, Université Libre de Bruxelles, Boulevard du Triomphe, C.P. 212, B-1050 Bruxelles, Belgium

Abstract: In order to speed up the synthesis of Petri nets from labelled transition systems, a divide and conquer strategy consists in defining decompositions of labelled transition systems, such that each component is synthesisable iff so is the original system. Then corresponding Petri Net composition operators are searched to combine the solutions of the various components into a solution of the original system. The paper presents two such techniques, which may be combined: products and articulations. They may also be used to structure transition systems, and to analyse the performance of synthesis techniques when applied to such structures.

Keywords: labelled transition systems, composition, decomposition, Petri net synthesis

DOI: 10.3233/FI-2021-2080

Journal: Fundamenta Informaticae, vol. 183, no. 1-2, pp. 1-31, 2021