In this paper we revisit some pioneering eorts to equip Petri nets with compact operational models for expressing causality. The models we propose have a bisimilarity relation and a minimal representative for each equivalence class, and they can be fully explained as coalgebras on a presheaf category on an index category of partial orders. First, we provide a set-theoretic model in the form of a a causal case graph, that is a labeled transition system where states and transitions represent markings and rings of the net, respectively, and are equipped with causal information. Most importantly, each state has a poset representing causal dependencies among past events. Our rst result shows the correspondence with behavior structure semantics as proposed by Trakhtenbrot and Rabinovich. Causal case graphs may be innitely-branchi ng and have innitely many states, but we show how they can be rened to get an equivalent nitely-branching model. In it, states only keep the most recent causes for each token, are up to isomorphism, and are equipped with a symmetry, i.e., a group of poset isomorphisms. Symmetries are essential for the existence of a minimal, often nite-state, model. This rst part requires no knowledge of category theory. The next step is constructing a coalgebraic model. We exploit the fact that events can be represented as names, and event generation as name generation. Thus we can apply the Fiore-Turi framework, where the semantics of nominal calculi are modeled as coalgebras over presheaves. We model causal relations as a suitable category of posets with action labels, and generation of new events with causal dependencies as an endofunctor on this category. Presheaves indexed by labeled posets represent the functorial association between states and their causal information. Then we dene a well-behaved category of coalgebras. Our coalgebraic model is still innite-state, but we exploit the equivalence between coalgebras over a class of presheaves and History Dependent automata to derive a compact representation, which is equivalent to our set-theoretical compact model. Remarkably, state reduction is automatically performed along the equivalence.
A first version of HD-automata for Petri nets, called , has been introduced in @cite_25 . However, their construction is purely set-theoretical and does not include symmetries, so the existence of a minimal model is not guaranteed. This version of HD-automata is similar to what we call immediate causes CG (without symmetries). HD-automata with symmetries were developed for the @math -calculus in @cite_20 @cite_15 , and a general categorical treatment was provided in @cite_2 . In all these cases nominal structures associated to states are just a sets of (event) names, whereas we have posets, which are more adequate to represent causal dependencies.
@cite_15 @cite_25 @cite_20 @cite_2
2091676842 2077397316 2152988203 2160106331
Automata-theoretic representations have proven useful in the automatic and exact analysis of computing systems. We propose a new semantical mapping of π-Calculus processes into place transition Petri nets. Our translation exploits the connections created by restricted names and can yield finite nets even for processes with unbounded name and unbounded process creation. The property of structural stationarity characterises the processes mapped to finite nets. We provide exact conditions for structural stationarity using novel characteristic functions. As application of the theory, we identify a rich syntactic class of structurally stationary processes, called finite handler processes. Our Petri net translation facilitates the automatic verification of a case study modelled in this class. The coalgebraic framework developed for the classical process algebras, and in particular its advantages concerning minimal realizations, does not fully apply to the π-calculus, due to the constraints on the freshly generated names that appear in the bisimulation.In this paper we propose to model the transition system of the π-calculus as a coalgebra on a category of name permutation algebras and to define its abstract semantics as the final coalgebra of such a category. We show that permutations are sufficient to represent in an explicit way fresh name generation, thus allowing for the definition of minimal realizations.We also link the coalgebraic semantics with a slightly improved version of history dependent (HD) automata, a model developed for verification purposes, where states have local names and transitions are decorated with names and name relations. HD-automata associated with agents with a bounded number of threads in their derivatives are finite and can be actually minimized. We show that the bisimulation relation in the coalgebraic context corresponds to the minimal HD-antomaton. 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. Abstract We present an approximation technique, that can render real-time model checking of safety and universal path properties more efficient. It is beneficial, when loops lead to repetition of control situations. Basically we augment a timed automata model with carefully selected extra transitions. This increases the size of the state-space, but potentially decreases the number of symbolic states to be explored by orders of magnitude. We give a formal definition of a timed automata formalism, enriched with basic data types, hand-shake synchronization, urgency, and committed locations. We prove by means of a trace semantics, that if a safety property can be established in the augmented model, it also holds for the original model. We extend our technique to a richer set of properties, that can be decided via a set of traces (universal path properties). In order for universal path properties to carry over to the original model, the semantics of the timed automata formalism is formulated relative to the applied augmentation. Our technique is particularly useful in systems, where a scheduler dictates repetition of control over elapsing time. As a typical example we mention translations of LEGO® RCX™ programs to U ppaal models, where the Round-Robin scheduler is a static entity. We allow scheduler and associated tasks to “park”, until some timing or environmental conditions are met. We apply our technique on a brick-sorter model for a safety property and report run-time data.