Algebraic Petri nets are a formalism for modeling distributed systems and algorithms, describing control and data flow by combining Petri nets and algebraic specification. One way to specify correctness of an algebraic Petri net model @math is to specify a linear equation @math over the places of @math based on term substitution, and coefficients from an abelian group @math . Then, @math is valid in @math iff @math is valid in each reachable marking of @math . Due to the expressive power of Algebraic Petri nets, validity is generally undecidable. Stable linear equations form a class of linear equations for which validity is decidable. Place invariants yield a well-understood but incomplete characterization of all stable linear equations. In this paper, we provide a complete characterization of stability for the subclass of homogeneous linear equations, by restricting ourselves to the interpretation of terms over the Herbrand structure without considering further equality axioms. Based thereon, we show that stability is decidable for homogeneous linear equations if @math is a cyclic group.
APNs or similar high level net''-formalisms are an established, expressive modeling language for distributed systems @cite_14 @cite_1 . Moreover, tools for Colored Petri Nets support simulation and (partial) verification @cite_9 @cite_11 . The idea to prove stable properties in Petri nets that use distinguishable tokens has been pursued at least since the early 80s @cite_3 . Ever since, the class of invariants became a substantial part of Petri Net analysis @cite_0 @cite_1 @cite_14 . Other stable properties for Algebraic Petri Nets have been studied in the context of Traps Co-Traps @cite_12 . In elementary Petri Nets (P T-Nets), stable properties such as traps and co-traps have been studied @cite_14 and been shown as useful for verification @cite_14 @cite_4 . Compared to this, the number of publications regarding stable properties in is comparatively small. In the last years, Petri Net variants with distinguishable tokens gained more attention to model data in distributed systems and applying analytic methods such as @cite_6 @cite_10 @cite_5 .
@cite_14 @cite_4 @cite_9 @cite_1 @cite_3 @cite_6 @cite_0 @cite_5 @cite_10 @cite_12 @cite_11
2152988203 1503128752 2151720555 1568573127
With their intuitive graphical approach and expressive analysis techniques, Petri nets are suitable for a wide range of applications and teaching scenarios, and they have gained wide acceptance as a modeling technique in areas such as software design and control engineering. The core theoretical principles have been studied for many decades and there is now a comprehensive research literature that complements the extensive implementation experience. In this book the author presents a clear, thorough introduction to the essentials of Petri nets. He explains the core modeling techniques and analysis methods and he illustrates their usefulness with examples and case studies. Part I describes how to use Petri nets for modeling; all concepts are explained with the help of examples, starting with a generic, powerful model which is also intuitive and realistic. Part II covers the essential analysis methods that are specific to Petri nets, introducing techniques used to formulate key properties of system nets and algorithms for proving their validity. Part III presents case studies, each introducing new concepts, properties and analysis techniques required for very different modeling tasks. The author offers different paths among the chapters and sections: the elementary strand for readers who wish to study only elementary nets; the modeling strand for those who wish to study the modeling but not the analysis of systems; and finally the elementary models of the modeling strand for those interested in technically simple, but challenging examples and case studies. The author achieves an excellent balance between consistency, comprehensibility and correctness in a book of distinctive design. Among its characteristics, formal arguments are reduced to a minimum in the main text with many of the theoretical formalisms moved to an appendix, the explanations are supported throughout with fully integrated graphical illustrations, and each chapter ends with exercises and recommendations for further reading. The book is suitable for students of computer science and related subjects such as engineering, and for a broad range of researchers and practitioners. We consider verification of safety properties for concurrent real-timed systems modelled as timed Petri nets by performing symbolic forward reachability analysis. We introduce a formalism, called region generators, for representing sets of markings of timed Petri nets. Region generators characterize downward closed sets of regions and provide exact abstractions of sets of reachable states with respect to safety properties. We show that the standard operations needed for performing symbolic reachability analysis are computable for region generators. Since forward reachability analysis is necessarily incomplete, we introduce an acceleration technique to make the procedure terminate more often on practical examples. We have implemented a prototype for analyzing timed Petri nets and used it to verify a parameterized version of Fischer's protocol, Lynch and Shavit's mutual exclusion protocol and a producer-consumer protocol. We also used the tool to extract finite-state abstractions of these protocols. We consider (unbounded) Timed Petri Nets (TPNs) where each token is equipped with a real-valued clock representing the "age" of the token. Each arc in the net is provided with a subinterval of the natural numbers, restricting the ages of the tokens travelling the arc. We apply a methodology developed in [AN00], based on the theory of better quasi orderings (BQOs), to derive an efficient constraint system for automatic verification of safety properties for TPNs. We have implemented a prototype based on our method and applied it for verification of a parametrized version of Fischer's protocol. Coloured Petri Nets (CPN) is a graphical language for modelling and validating concurrent and distributed systems, and other systems in which concurrency plays a major role. The development of such systems is particularly challenging because of inherent intricacies like possible nondeterminism and the immense number of possible execution sequences. In this textbook Jensen and Kristensen introduce the constructs of the CPN modelling language and present the related analysis methods in detail. They also provide a comprehensive road map for the practical use of CPN by showcasing selected industrial case studies that illustrate the practical use of CPN modelling and validation for design, specification, simulation, verification and implementation in various application domains. Their presentation primarily aims at readers interested in the practical use of CPN. Thus all concepts and constructs are first informally introduced through examples and then followed by formal definitions (which may be skipped). The book is ideally suitable for a one-semester course at an advanced undergraduate or graduate level, and through its strong application examples can also serve for self-study. An accompanying website offers additional material such as slides, exercises and project proposals. Book website:http: www.cs.au.dk CPnets cpnbook