Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUndecidability of performance equivalence of Petri nets
197
0
0.0
(
0
)
Added by
S{\\l}awomir Lasota
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate bisimulation equivalence on Petri nets under durational semantics. Our motivation was to verify the conjecture that in durational setting, the bisimulation equivalence checking problem becomes more tractable than in ordinary setting (which is the case, e.g., over communication-free nets). We disprove this conjecture in three of four proposed variants of durational semantics. The fourth variant remains an intriguing open problem.
rate research
Read More
The categorical modeling of Petri nets has received much attention recently. The Dialectica construction has also had its fair share of attention. We revisit the use of the Dialectica construction as a categorical model for Petri nets generalizing the original application to suggest that Petri nets with different kinds of transitions can be modeled in the same categorical framework. Transitions representing truth-values, probabilities, rates or multiplicities, evaluated in different algebraic structures called lineales are useful and are modeled here in the same category. We investigate (categorical instances of) this generalized model and its connections to more recent models of categorical nets.
We consider approaches for causal semantics of Petri nets, explicitly representing dependencies between transition occurrences. For one-safe nets or condition/event-systems, the notion of process as defined by Carl Adam Petri provides a notion of a run of a system where causal dependencies are reflected in terms of a partial order. A well-known problem is how to generalise this notion for nets where places may carry several tokens. Goltz and Reisig have defined such a generalisation by distinguishing tokens according to their causal history. However, this so-called individual token interpretation is often considered too detailed. A number of approaches have tackled the problem of defining a more abstract notion of process, thereby obtaining a so-called collective token interpretation. Here we give a short overview on these attempts and then identify a subclass of Petri nets, called structural conflict nets, where the interplay between conflict and concurrency due to token multiplicity does not occur. For this subclass, we define abstract processes as equivalence classes of Goltz-Reisig processes. We justify this approach by showing that we obtain exactly one maximal abstract process if and only if the underlying net is conflict-free with respect to a canonical notion of conflict.
We prove that $omega$-languages of (non-deterministic) Petri nets and $omega$-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of $omega$-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of $omega$-languages of (non-deterministic) Turing machines which also form the class of effective analytic sets. In particular, for each non-null recursive ordinal $alpha < omega_1^{{rm CK}} $ there exist some ${bf Sigma}^0_alpha$-complete and some ${bf Pi}^0_alpha$-complete $omega$-languages of Petri nets, and the supremum of the set of Borel ranks of $omega$-languages of Petri nets is the ordinal $gamma_2^1$, which is strictly greater than the first non-recursive ordinal $omega_1^{{rm CK}}$. We also prove that there are some ${bf Sigma}_1^1$-complete, hence non-Borel, $omega$-languages of Petri nets, and that it is consistent with ZFC that there exist some $omega$-languages of Petri nets which are neither Borel nor ${bf Sigma}_1^1$-complete. This answers the question of the topological complexity of $omega$-languages of (non-deterministic) Petri nets which was left open in [DFR14,FS14].
We study detectability properties for labeled Petri nets and finite automata. We first study weak approximate detectability (WAD) that implies that there exists an infinite observed output sequence of the system such that each prefix of the output sequence with length greater than a given value allows an observer to determine if the current state belongs to a given set. We also consider two new concepts called instant strong detectability (ISD) and eventual strong detectability (ESD). The former property implies that for each possible infinite observed output sequence each prefix of the output sequence allows reconstructing the current state. The latter implies that for each possible infinite observed output sequence, there exists a value such that each prefix of the output sequence with length greater than that value allows reconstructing the current state. Results: WAD: undecidable for labeled Petri nets, PSPACE-complete for finite automata ISD: decidable and EXPSPACE-hard for labeled Petri nets, belongs to P for finite automata ESD: decidable under promptness assumption and EXPSPACE-hard for labeled Petri nets, belongs to P for finite automata SD: belongs to P for finite automata, strengthens Shu and Lins 2011 results based on two assumptions of deadlock-freeness and promptness ISD<SD<ESD<WD<WAD for both labeled Petri nets and finite automata
Petri networks and network models are two frameworks for the compositional design of systems of interacting entities. Here we show how to combine them using the concept of a catalyst: an entity that is neither destroyed nor created by any process it engages in. In a Petri net, a place is a catalyst if its in-degree equals its out-degree for every transition. We show how a Petri net with a chosen set of catalysts gives a network model. This network model maps any list of catalysts from the chosen set to the category whose morphisms are all the processes enabled by this list of catalysts. Applying the Grothendieck construction, we obtain a category fibered over the category whose objects are lists of catalysts. This category has as morphisms all processes enabled by some list of catalysts. While this category has a symmetric monoidal structure that describes doing processes in parallel, its fibers also have premonoidal structures that describe doing one process and then another while reusing the catalysts.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
