I mean an approach to find all concurrent transitions directly from a Petri net structure.
Evolving Concurrent Petri Net Models of Epistasis
http://researchcommons.waikato.ac.nz/bitstream/handle/10289/3492/ACIID%202010%20Final%20Version.pdf;jsessionid=757CF60636C04AC38A0651C09D8A09D3?sequence=1
Modelling Concurrent Computations:
from Contextual Petri Nets
to Graph Grammars
http://localwww.math.unipd.it/~baldan/Papers/Soft-copy-pdf/TesiHyperref.pdf
Sets of transitions that can be fired in one step depend only on the current marking.
It is clearly visible for PT nets. Please consult the paper by Murata "Petri nets: Properties, analysis and applications" and in particular equations 2-5.
In consequence, to determnie sets of potenially parallel transitions, you should:
However, I am not sure if the problem decidable in case of unbounded nets represented by coverability graphs.
The problem is decidable, it's the coverability problem. To check whether several transitions can fire simultaniously one needs to check, that a marking covering the sum of all presets for these transitions is reachable.
Consult the paper http://www.sciencedirect.com/science/article/pii/0890540190900097
For calculating concurrent transitions from the Petri net structure I invite you to see several works of François Vernadat (LAAS-CNRS) where an approach for constructing the covered step graph is proposed. However this approach can’t find all instances of concurrent transitions that may be occurred during the system execution (dynamic behavior). For considering all kinds of concurrent transitions I suggest to use the true concurrency model “Maximality-based labeled transition systems” which implements a maximality semantics. This model has been used for the definition of the semantics of place transition Petri nets and recently for Recursive Petri nets (Djamel Eddine Saidouni, Messaouda Bouneb and Jean Michel Ilié). Also a maximality-based step graph structure has been defined in which each transition gives a set of concurrent transitions that may be executed simultaneously (Adel Benamira and Djamel Eddine Saidouni).
when you said: "directly from a Petri net structure", did you mean that you are not interested to those approaches based on coverbaility or rechability trees? are you looking for strutural analysis only, without considering any intial marking of the net?
In this case, one possible solution is to use concurrent semantics, of Petri nets, which shows explicitly dependancies between transition occurrences. This last semantics can be studied, may be, using an occurence graph instead of the reachability tree or the coverbality graph. If I have understood, well the problem, then I think that this was discussed early (1998) in one fondamenal paper (section 6, page 37): http://www.cmi.ac.in/~madhavan/courses/acts2010/desel-reisig-ptnets.pdf
- Badges
- Science topic