Decidability Issues for Petri Nets -- a survey 1 1 1 A former version of this paper appeared in the Concurrency Column of the EATCS Bulletin 52. Javier Esparza ∗ Mogens Nielsen Institut für Informatik BRICS ∗∗ Technische Universität München Computer Science Department Arcisstr. 21 Aarhus University
2024
Read Decidability Issues for Petri Nets -- a survey 1 1 1 A former version of this paper appeared in the Concurrency Column of the EATCS Bulletin 52. Javier Esparza ∗ Mogens Nielsen Institut für Informatik BRICS ∗∗ Technische Universität München Computer Science Department Arcisstr. 21 Aarhus University (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01592.txt.
Description
Abstract We survey 25 years of research on decidability issues for Petri nets. We collect results on the decidability of important properties, equivalence notions, and temporal logics. 1 Introduction Petri nets are one of the most popular formal models for the representation and analysis of parallel processes. They are due to C.A.
Catalog record
| YEAR | 2024 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01592
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Decidability Issues for Petri Nets -- a survey 1 1 1 A former version of this paper appeared in the Concurrency Column of the EATCS Bulletin 52. Javier Esparza ∗ Mogens Nielsen Institut für Informatik BRICS ∗∗ Technische Universität München Computer Science Department Arcisstr. 21 Aarhus University D-80290 München Ny Munkegade, Bldg. 540 Germany DK-8000 Aarhus C Denmark Abstract We survey 25 years of research on decidability issues for Petri nets. We collect results on the decidability of important properties, equivalence notions, and temporal logics. 1 Introduction Petri nets are one of the most popular formal models for the representation and analysis of parallel processes. They are due to C.A. Petri, who introduced them in his doctoral dissertation in 1962. Some years later, and independently from Petri’s work, Karp and Miller introduced vector addition systems [ 47 ] , a simple mathematical structure which they used to analyse the properties of ‘parallel program schemata’, a model for parallel computation. In their seminal paper on parallel program schemata, Karp and Miller studied some decidability issues for vector addition systems, and the topic continued to be investigated by other researchers. When Petri’s ideas reached the States around 1970, it was observed that Petri nets and vector addition systems were mathematically equivalent, even though their underlying philosophical ideas were rather different (a computational approach to the physical world in Petri’s view, a formal model for concurrent programming in Karp and Miller’s). This gave more momentum to the research on decidability questions for Petri nets, which has since continued at a steady pace. In the following we have collected some highlights of decidability issues for Petri nets from the 70’s, 80’s and 90’s. As you will see, they form a nice mixture of old celebrated breakthroughs, and a recent burst of exciting new developments. We have decided to group our selected results in three sections, covering respectively the decidability of specific properties , various (behavioural) equivalences , and finally the model checking problem for temporal logics . ∗ This paper was written while this author was at the University of Edinburgh. ∗∗ Basic Research In Computer Science, Centre of the Danish National Research Foundation. It should be noted that we have selected our highlights also aiming at some coherence in our presentation. In other words, we do not claim to cover all important contributions on decidability for Petri nets, but still our selection covers a pretty comprehensive part of existing results, also compared to other similar surveys, e.g. [ 44 ] . We have not included results on extensions of the Petri net model. In particular, for decidability results on timed Petri nets we refer the reader to [ 46 , 78 , 79 ] . 2 Basic definitions We give, in a somewhat informal way, the basic definitions on Petri nets that we need in order to state the results of this overview. A net N is a triple (S,T,F) , where S and T are two disjoint, finite sets, and F is a relation on S\cup T such that F\cap(S\times S)=F\cap(T\times T)=\emptyset . The elements of S and T are called places and transitions , respectively, and the elements of F are called arcs . A marking of a net N=(S,T,F) is a mapping M\colon S\to{\mbox{$I\!\!N$}} . A marking M enables a transition t if it marks all its input places. If t is enabled at M , then it can occur , and its occurrence leads to the successor marking M^{\prime} , which is defined for every place s as follows: a token is removed from each input place of t and a token is added to each output place of t (if a place is both input and output place of a transition, then its number of tokens does not change). This is denoted by M\stackrel{{\scriptstyle t}}{{\longrightarrow}}M^{\prime} . A Petri net is a pair (N,M_{0}) , where N is a net and M_{0} a marking of N , called initial marking . A sequence M_{0}\stackrel{{\scriptstyle t_{1}}}{{\longrightarrow}}M_{1}\stackrel{{\scriptstyle t_{2}}}{{\longrightarrow}}\cdots\stackrel{{\scriptstyle t_{n}}}{{\longrightarrow}}M_{n} is a finite occurrence sequence leading from M to M_{n} and we write M_{0}\stackrel{{\scriptstyle t_{1}\ldots t_{n}}}{{-\!\!\!-\!\!\!\longrightarrow}}M_{n} . A sequence M_{0}\stackrel{{\scriptstyle t_{1}}}{{\longrightarrow}}M_{1}\stackrel{{\scriptstyle t_{2}}}{{\longrightarrow}}\cdots is an infinite occurrence sequence . An occurrence sequence is maximal if it is infinite, or it leads to a marking which does not enable any transition. A marking M of N is reachable if M_{0}\stackrel{{\scriptstyle\sigma}}{{\longrightarrow}}M for some sequence \sigma . The reachability graph of a Petri net is a labelled graph whose nodes are the reachable markings; given two reachable markings M , M^{\prime} , the reachability graph contains an edge from M to M^{\prime} labelled by a transition t if and only if M\stackrel{{\scriptstyle t}}{{\longrightarrow}}M^{\prime} . A labelled net is a quadruple (S,T,F,\ell) , where (S,T,F) is a net and \ell is a labeling function which assigns a letter of some alphabet to each transition. This function need not be injective. The reachability graph of a labelled net is defined like that of unlabelled nets; the only difference is that if M\stackrel{{\scriptstyle t}}{{\longrightarrow}}M^{\prime} then the corresponding edge from M to M^{\prime} is labelled by \ell(t) . Sometimes we refer to the ‘normal’ Petri nets as unlabelled Petri nets. Unlabelled Petri nets can also be seen as labelled Petri nets in which the labelling function is injective. Given a Petri net (N,M_{0}) and a marking M^{f} of N (called final marking ), we define the language of (N,M_{0}) with respect to M^{f} as \displaystyle L(N,M_{0},M^{f}) \displaystyle= \displaystyle\{\sigma\mid M_{0}\stackrel{{\scriptstyle\sigma}}{{\longrightarrow}}M^{f}\} and the trace set of (N,M_{0}) as \displaystyle T(N,M_{0}) \displaystyle= \displaystyle\{\sigma\mid M_{0}\stackrel{{\scriptstyle\sigma}}{{\longrightarrow}}M\mbox{ for some marking $M$}\} (sometimes the terms ‘language’ and ‘terminal language’ are used instead of ‘trace set’ and ‘language’). Please note that the term ‘trace’ is also used in the theory of Petri nets for elements of a free partially commutative monoid, following an idea originally due to Mazurkiewicz [ 60 ] . In order to focus our presentation, we have chosen not to include decidability results on ‘Mazurkiewicz traces’. Given a labelled Petri net (N,M_{0}) , where N=(S,T,F,\ell) , and a marking M^{f} of N , the language of (N,M_{0}) with respect to M^{f} as \displaystyle L(N,M_{0},M^{f}) \displaystyle= \displaystyle\{\ell(\sigma)\mid M_{0}\stackrel{{\scriptstyle\sigma}}{{\longrightarrow}}M^{f}\} and the trace set of (N,M_{0}) is defined as \displaystyle T(N,M_{0}) \displaystyle= \displaystyle\{\ell(\sigma)\mid M_{0}\stackrel{{\scriptstyle\sigma}}{{\longrightarrow}}M\mbox{ for some marking $M$}\} We now define those classes of nets that are mentioned several times along the survey. Some others, which appear only once, are defined on the fly (or a reference is given). A Petri net (N,M_{0}) is: • persistent if for any two different transitions t_{1} , t_{2} of N and any reachable marking M , if t_{1} and t_{2} are enabled at M , then the occurrence of one cannot disable the other. • conflict-free if, for every place s with more than one output transition, every output transition of s is also one of its input transitions. All conflict-free nets are persistent; in fact, (N,M_{0}) is conflict-free if and only if (N,M) is persistent for every marking M of N . For most purposes, this class is equivalent to the class of nets in which each place has at most one output transition. • sinkless if any cycle of N which is marked at M_{0} (meaning that M_{0}(s)>0 for