Abstract | ||
---|---|---|
We show that the downward-closure of a Petri net language is effectively computable. This is mainly done by using the notions defined for showing decidability of the reachability problem of Petri nets. In particular, we rely on Lambert's construction of marked graph transition sequences -- special instances of coverability graphs that allow us to extract constructively the simple regular expression corresponding to the downward-closure. We also consider the remaining language types for Petri nets common in the literature. For all of them, we provide algorithms that compute the simple regular expressions of their downwardclosure. As application, we outline an algorithm to automatically analyse the stability of a system against attacks from a malicious environment. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-14162-1_39 | ICALP (2) |
Keywords | Field | DocType |
petri net,special instance,coverability graph,malicious environment,marked graph transition sequence,simple regular expression,reachability problem,remaining language type,regular expression | Marked graph,Downward closure,Discrete mathematics,Regular expression,Combinatorics,Petri net,Computer science,Theoretical computer science,Decidability,Stochastic Petri net,Process architecture,Reachability problem | Conference |
Volume | ISSN | ISBN |
6199 | 0302-9743 | 3-642-14161-7 |
Citations | PageRank | References |
15 | 0.62 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peter Habermehl | 1 | 67 | 3.50 |
Roland Meyer | 2 | 203 | 15.99 |
Harro Wimmel | 3 | 114 | 11.56 |