Skip to Main content Skip to Navigation
Journal articles

Analysis and Synthesis of Weighted Marked Graph Petri Nets: Exact and Approximate Methods

Abstract : Numerous real-world systems can be modeled with Petri nets, which allow a combination of concurrency with synchronizations and conflicts. To alleviate the difficulty of checking their behaviour, a common approach consists in studying specific subclasses. In the converse problem of Petri net synthesis, a Petri net of some subclass has to be constructed efficiently from a given specification, typically from a labelled transition system (lts) describing the behaviour of the desired net. In this paper, we focus on a notorious subclass of persistent Petri nets, the weighted marked graphs (WMGs), also called generalised (or weighted) event (or marked) graphs or weighted T-nets. In such nets, edges have multiplicities (weights) and each place has at most one ingoing and one outgoing transition. Although extensively studied in previous works and benefiting from strong results, both their analysis and synthesis can be further investigated. We provide new behavioural properties of WMGs expressed on their reachability graph, notably backward persistence and strong similarities between any two sequences sharing the same starting state and the same destination state. Besides, we design a general synthesis procedure aiming at the WMG class. Finally, when no solution to the synthesis problem exists, i.e., when the given lts is not WMG-solvable, we show how to construct a WMG whose reachability graph is a minimal over-approximation of the given lts.
Document type :
Journal articles
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download

https://hal.laas.fr/hal-02332309
Contributor : Thomas Hujsa <>
Submitted on : Thursday, October 24, 2019 - 5:04:54 PM
Last modification on : Thursday, June 10, 2021 - 3:02:02 AM
Long-term archiving on: : Saturday, January 25, 2020 - 5:35:37 PM

File

WMG-FI-DH.pdf
Files produced by the author(s)

Identifiers

Citation

Raymond Devillers, Thomas Hujsa. Analysis and Synthesis of Weighted Marked Graph Petri Nets: Exact and Approximate Methods. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2019, 169 (1-2), pp.1 - 30. ⟨10.3233/FI-2019-1837⟩. ⟨hal-02332309⟩

Share

Metrics

Record views

109

Files downloads

182