The Experts below are selected from a list of 61944 Experts worldwide ranked by ideXlab platform
Wolfgang Reisig - One of the best experts on this subject based on the ideXlab platform.
-
place transition Petri Nets
Lecture Notes in Computer Science, 1998Co-Authors: Jörg Desel, Wolfgang ReisigAbstract:This contributions provides an introduction to the theory of place/transition Petri Nets. Topics include the sequential and the concurrent behavior of place/transition Petri Nets, marking graphs and coverability trees, and some analysis techniques that are based on the structure of place/transition Petri Nets.
-
Petri Nets - Place or Transition Petri Nets
Lectures on Petri Nets I: Basic Models, 1998Co-Authors: Jörg Desel, Wolfgang ReisigAbstract:This contributions provides an introduction to the theory of place/transition Petri Nets. Topics include the sequential and the concurrent behavior of place/ transition Petri Nets, marking graphs and coverability trees, and some analysis techniques that are based on the structure of place/transition Petri Nets.
-
Application and Theory of Petri Nets - Combining Petri Nets and Other Formal Methods
Application and Theory of Petri Nets 1992, 1992Co-Authors: Wolfgang ReisigAbstract:Several practically important concepts, supporting proper treatment of concurrency, have evolved during the recent years. Many of them have been presented in formal settings different from Petri Nets. In this paper we exemplify some of those concepts and relate them to the state-of-the-art in Petri Nets.
-
Petri Nets and algebraic specifications
Theoretical Computer Science, 1991Co-Authors: Wolfgang ReisigAbstract:Reisig, W., Petri Nets and algebraic specifications, Theoretical Computer Science 80 (1991) 1-34. Petri Nets gain a great deal of modelling power by representing dynamically changing items as structured tokens (instead of “black dots”). Algebraic specifications turned out adequate for dealing with structured items. We will use this formalism to construct Petri Nets with structured tokens. Place- and transition-invariants are useful analysis techniques for conventional Petri Nets. We derive corresponding formalisms for Nets with structured tokens, based on term substitution.
Louis E. Rosier - One of the best experts on this subject based on the ideXlab platform.
-
Bounded self-stabilizing Petri Nets
Acta Informatica, 1995Co-Authors: Ludmila Cherkasova, Rodney R. Howell, Louis E. RosierAbstract:We investigate the property of self-stabilization in bounded Petri Nets. We give characterizations for both self-stabilizing bounded ordinary Petri Nets (i.e., Petri Nets without multiple arcs) and self-stabilizing bounded general Petri Nets (i.e., Petri Nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri Nets and PSPACE-complete for bounded general Petri Nets.
-
Bounded self-stabilizing Petri Nets
Acta Informatica, 1995Co-Authors: Ludmila Cherkasova, Rodney R. Howell, Louis E. RosierAbstract:We investigate the property of self-stabilization in bounded Petri Nets. We give characterizations for both self-stabilizing bounded ordinary Petri Nets (i.e., Petri Nets without multiple arcs) and self-stabilizing bounded general Petri Nets (i.e., Petri Nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri Nets and PSPACE-complete for bounded general Petri Nets.
-
Applications and Theory of Petri Nets - Bounded Self-Stabilizing Petri Nets
Advances in Petri Nets 1993, 1993Co-Authors: Ludmila Cherkasova, Rodney R. Howell, Louis E. RosierAbstract:We investigate the property of self-stabilization in bounded Petri Nets. We give characterizations for both self-stabilizing bounded ordinary Petri Nets (i.e., Petri Nets without multiple arcs) and self-stabilizing bounded general Petri Nets (i.e., Petri Nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri Nets and PSPACE-complete for bounded general Petri Nets.
-
Normal and sinkless Petri Nets
Journal of Computer and System Sciences, 1993Co-Authors: Rodney R. Howell, Louis E. Rosier, Hsu-chun YenAbstract:We examine both the modeling power of normal and sinkless Petri Nets and the computational complexities of various classical decision problems with respect to these two classes. We argue that although neither normal nor sinkless Petri Nets are strictly more powerful than persistent Petri Nets, they nonetheless are both capable of modeling a more interesting class of problems. On the other hand, we give strong evidence that normal and sinkless Petri Nets are easier to analyze than persistent Petri Nets. In so doing, we apply techniques originally developed for conflict-free Petri Nets — a class defined solely in terms of the structure of the net — to sinkless Petri Nets — a class defined in terms of the behavior of the net. As a result, we give the first comprehensive complexity analysis of a class of potentially unbounded Petri Nets defined in terms of their behavior.
-
Completeness Results for Single-Path Petri Nets
Information and Computation, 1993Co-Authors: Rodney R. Howell, Petr Jancar, Louis E. RosierAbstract:We define a new subclass of persistent Petri Nets called single-path Petri Nets. Our intention is to provide a class of Petri Nets whose study might yield some insight into the mathematical properties of persistent Petri Nets or even general Petri Nets. We conjecture that the Karp-Miller coverability tree for a persistent net is small enough to be searched in polynomial space. Although we are unable to prove this conjecture, we do show that single-path Petri Nets have this property. We then use this fact to show that the canonical analysis problems (i.e., boundedness, reachability, containment, and equivalence) for single-path Petri Nets are PSPACE-complete in the strong sense. Furthermore, we show that the problem of recognizing a single-path Petri net is also PSPACE-complete.
Rodney R. Howell - One of the best experts on this subject based on the ideXlab platform.
-
Bounded self-stabilizing Petri Nets
Acta Informatica, 1995Co-Authors: Ludmila Cherkasova, Rodney R. Howell, Louis E. RosierAbstract:We investigate the property of self-stabilization in bounded Petri Nets. We give characterizations for both self-stabilizing bounded ordinary Petri Nets (i.e., Petri Nets without multiple arcs) and self-stabilizing bounded general Petri Nets (i.e., Petri Nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri Nets and PSPACE-complete for bounded general Petri Nets.
-
Bounded self-stabilizing Petri Nets
Acta Informatica, 1995Co-Authors: Ludmila Cherkasova, Rodney R. Howell, Louis E. RosierAbstract:We investigate the property of self-stabilization in bounded Petri Nets. We give characterizations for both self-stabilizing bounded ordinary Petri Nets (i.e., Petri Nets without multiple arcs) and self-stabilizing bounded general Petri Nets (i.e., Petri Nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri Nets and PSPACE-complete for bounded general Petri Nets.
-
Applications and Theory of Petri Nets - Bounded Self-Stabilizing Petri Nets
Advances in Petri Nets 1993, 1993Co-Authors: Ludmila Cherkasova, Rodney R. Howell, Louis E. RosierAbstract:We investigate the property of self-stabilization in bounded Petri Nets. We give characterizations for both self-stabilizing bounded ordinary Petri Nets (i.e., Petri Nets without multiple arcs) and self-stabilizing bounded general Petri Nets (i.e., Petri Nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri Nets and PSPACE-complete for bounded general Petri Nets.
-
Normal and sinkless Petri Nets
Journal of Computer and System Sciences, 1993Co-Authors: Rodney R. Howell, Louis E. Rosier, Hsu-chun YenAbstract:We examine both the modeling power of normal and sinkless Petri Nets and the computational complexities of various classical decision problems with respect to these two classes. We argue that although neither normal nor sinkless Petri Nets are strictly more powerful than persistent Petri Nets, they nonetheless are both capable of modeling a more interesting class of problems. On the other hand, we give strong evidence that normal and sinkless Petri Nets are easier to analyze than persistent Petri Nets. In so doing, we apply techniques originally developed for conflict-free Petri Nets — a class defined solely in terms of the structure of the net — to sinkless Petri Nets — a class defined in terms of the behavior of the net. As a result, we give the first comprehensive complexity analysis of a class of potentially unbounded Petri Nets defined in terms of their behavior.
-
Completeness Results for Single-Path Petri Nets
Information and Computation, 1993Co-Authors: Rodney R. Howell, Petr Jancar, Louis E. RosierAbstract:We define a new subclass of persistent Petri Nets called single-path Petri Nets. Our intention is to provide a class of Petri Nets whose study might yield some insight into the mathematical properties of persistent Petri Nets or even general Petri Nets. We conjecture that the Karp-Miller coverability tree for a persistent net is small enough to be searched in polynomial space. Although we are unable to prove this conjecture, we do show that single-path Petri Nets have this property. We then use this fact to show that the canonical analysis problems (i.e., boundedness, reachability, containment, and equivalence) for single-path Petri Nets are PSPACE-complete in the strong sense. Furthermore, we show that the problem of recognizing a single-path Petri net is also PSPACE-complete.
Hsu-chun Yen - One of the best experts on this subject based on the ideXlab platform.
-
Petri Nets with Simple Circuits
IEICE Transactions on Information and Systems, 2005Co-Authors: Hsu-chun YenAbstract:We study the complexity of the reachability problem for a new subclass of Petri Nets called simple-circuit Petri Nets, which properly contains several well known subclasses such as conflict-free, BPP, normal Petri Nets and more. A new decomposition approach is applied to developing an integer linear programming formulation for characterizing the reachability sets of such Petri Nets. Consequently, the reachability problem is shown to be NP-complete. The model checking problem for some temporal logics is also investigated for simple-circuit Petri Nets.
-
COCOON - Petri Nets with simple circuits
Lecture Notes in Computer Science, 2003Co-Authors: Hsu-chun YenAbstract:We study the complexity of the reachability problem for a new subclass of Petri Nets called simple-circuit Petri Nets, which properly contains several well known subclasses such as conflict-free, BPP, normal Petri Nets and more. A new decomposition approach is applied to developing an integer linear programming formulation for characterizing the reachability sets of such Petri Nets. Consequently, the reachability problem is shown to be NP-complete. The model checking problem for some temporal logics is also investigated for simple-circuit Petri Nets.
-
Priority conflict-free Petri Nets
Acta Informatica, 1998Co-Authors: Hsu-chun YenAbstract:A number of problems concerning priority conflict-free Petri Nets are investigated in this paper. We show the reachability problem for such Petri Nets to be NP-complete. (Using a similar technique, the NP-completeness result applies to the class of priority BPP-Nets as well.) As for the boundedness problem, an NP-completeness result is demonstrated for priority conflict-free Petri Nets with two types of prioritized transitions. (In contrast, the problem is known to be P-complete for conflict-free Petri Nets without priorities.) We also investigate the home state problem, i.e., the problem of determining whether home states exist in a given a Petri net, for conflict-free Petri Nets with and without priorities. As it turns out, home states always exist for bounded conflict-free Petri Nets without priorities. If an additional liveness constraint is imposed, such Petri Nets are guaranteed to be ‘reversible’ (i.e., their initial states are home states). For priority conflict-free Petri Nets, being bounded and live is sufficient for the existence of home states. However, if the liveness assumption is dropped, the existence of home states is no longer guaranteed.
-
Normal and sinkless Petri Nets
Journal of Computer and System Sciences, 1993Co-Authors: Rodney R. Howell, Louis E. Rosier, Hsu-chun YenAbstract:We examine both the modeling power of normal and sinkless Petri Nets and the computational complexities of various classical decision problems with respect to these two classes. We argue that although neither normal nor sinkless Petri Nets are strictly more powerful than persistent Petri Nets, they nonetheless are both capable of modeling a more interesting class of problems. On the other hand, we give strong evidence that normal and sinkless Petri Nets are easier to analyze than persistent Petri Nets. In so doing, we apply techniques originally developed for conflict-free Petri Nets — a class defined solely in terms of the structure of the net — to sinkless Petri Nets — a class defined in terms of the behavior of the net. As a result, we give the first comprehensive complexity analysis of a class of potentially unbounded Petri Nets defined in terms of their behavior.
-
Application and Theory of Petri Nets - A Unified Approach for Reasoning about Conflict-Free Petri Nets
Application and Theory of Petri Nets 1993, 1993Co-Authors: Hsu-chun Yen, Bow-yaw Wang, Ming-sheng YangAbstract:The aim of this paper is to develop a unified approach for deriving complexity results for problems concerning conflict-free Petri Nets. To do so, we first define a class of formulas for paths in Petri Nets. We then show that answering the satisfiability problem for conflictfree Petri Nets is tantamount to solving a system of linear inequalities (which is known to be in P). Since a wide spectrum of Petri net problems (including various fairness-related problems) can be reduced to the satisfiability problem in a straightforward manner, our approach offers an umbrella under which many Petri net problems for conflict-free Petri Nets can be shown to be solvable in polynomial time. As a side-product, our analysis provides evidence as to why detecting unboundedness for conflict-free Petri Nets is easier (provided P ≠ NP) than for normal and sinkless Petri Nets (which are two classes that properly contain that of conflict-free Petri Nets).
Jörg Desel - One of the best experts on this subject based on the ideXlab platform.
-
Petri Nets - Place or Transition Petri Nets
Lectures on Petri Nets I: Basic Models, 1998Co-Authors: Jörg Desel, Wolfgang ReisigAbstract:This contributions provides an introduction to the theory of place/transition Petri Nets. Topics include the sequential and the concurrent behavior of place/ transition Petri Nets, marking graphs and coverability trees, and some analysis techniques that are based on the structure of place/transition Petri Nets.
-
place transition Petri Nets
Lecture Notes in Computer Science, 1998Co-Authors: Jörg Desel, Wolfgang ReisigAbstract:This contributions provides an introduction to the theory of place/transition Petri Nets. Topics include the sequential and the concurrent behavior of place/transition Petri Nets, marking graphs and coverability trees, and some analysis techniques that are based on the structure of place/transition Petri Nets.
