Symbolic execution of concurrent systems using Petri nets

Techniques for analyzing sequential programs in order to improve their reliability have been widely studied in the past. Among the most interesting analysis techniques, we consider symbolic execution. However, analysis techniques for concurrent programs, and in particular symbolic execution, are still an open research area. In this paper, we define a method for symbolic execution of concurrent systems, based on an extension of the Petri net formalism, called EF nets. EF nets are a powerful, highly expressive and general formalism. Depending on the level of abstraction of actions and predicates that one associates to the transitions of the net, EF nets can be used as a high-level specification formalism for concurrent systems, or as a lower level internal representation of concurrent programs. Thus, the model is not dependent on a particular concurrent programming language, but it is flexible enough to be the kernel model for the representation of a wide set of systems and programming languages. In the paper, in order to support the analysis of a concurrent system or program, at first a general algorithm for symbolically executing an EF net is defined. Then, a more efficient algorithm is given for the particular, though important, subclass of EF nets, defined as safe EF nets. Such algorithm is proved to significantly help in reducing the amount of information needed to characterize a symbolic execution. Both the modelling power of the EF nets and the usefulness of the concurrent symbolic execution algorithms defined are illustrated by means of a case study.     

Formalization of UML state machines using temporal logic

The main purpose of this paper is to approach the use of formal methods in computing. In more specific terms, we use a temporal logic to formalize the most fundamental aspects of the semantics of UML state machines. We pay special attention to the dynamic aspects of the different operations associated with states and transitions, as well as the behaviour of transitions related with composite states. This, to the best of our knowledge, has not been done heretofore using temporal logic.Our formalization is based on a temporal logic that combines points, intervals, and dates. Moreover this new temporal logic is built over an innovative and simple topological semantics, which simplifies the metatheory development.     

Properties of enhanced mobile membranes via coloured Petri nets

Enhanced mobile membranes represent a rule-based formalism involving parallelism and mobility dependent on available resources. A translation of this formalism into coloured Petri nets is provided in order to analyse some important properties (reachability, boundedness, liveness, fairness) in enhanced mobile membranes.     

Institutionalising UML 2.0 state machines

A key challenge to achieve a unified semantics for UML is how to handle the heterogeneity of its sublanguages. In this context, the theory of institutions provides an elegant and robust framework for programming in the large and in particular for compositionality. It can be used to define a family of formalisms which capture various UML sublanguages, and morphisms that represent the expected semantic relationships between them, resulting in a heterogeneous environment for the semantic definition of UML. The main goal of this work is to collaborate with the definition of such environment. For this purpose, we define an institution for UML 2.0 state machines. The building blocks of our institution are based on a previous semantics dealing with processing simple input events within a transition step. We also extend these semantic definitions for handling sequences of events, and then for considering runs through the state machine.     

Distributed dynamic programming using concurrent object-orientedness with actors visualized by high-level Petri nets

This paper deals with application of concurrent object-oriented programming with Actors to solve dynamic programming problems in a distributed computing environment. This area of research is often called distributed artificial intelligence. Using a dynamic programming example of chained matrix multiplication, a method of managing dynamic programming searches in a distributed programming environment with Actors is presented. Distributed computations with Actors are visualized by means of Time-Varying Automata (for cases with no intra-actor concurrency) or using a class of high-level nets called Hierarchical Colored Petri Nets (for cases with intra-actor concurrency). Design and implementation features of the specific Actor-based programming environment, using a concurrent extension of C++, are also discussed.     

Formal requirements modelling with executable use cases and coloured Petri nets

This paper presents executable use cases (EUCs), which constitute a model-based approach to requirements engineering. EUCs may be used as a supplement to model-driven development (MDD) and can describe and link user-level requirements and more technical software specifications. In MDD, user-level requirements are not always explicitly described, since usually it is sufficient that one provides a specification, or platform-independent model, of the software that is to be developed. Therefore, a combination of EUCs and MDD may have potential to cover the path from user-level requirements via specifications to implementations of computer-based systems.     

Performance analysis using Petri nets

The purpose of this paper is to focus on the implementation issues associated with using Petri nets for the performance analysis of discrete event dynamic systems while demonstrating several applications in manufacturing systems. Practical modeling issues will be discussed and several applications will be presented that illustrate the advantages and limitations of this methodology. These issues lead to the definition of several research problems in Petri nets for performance analysis.     

Synthesis of state machine diagrams from communication diagrams using Petri nets

Service-oriented architecture is an architecture style to build up a large-scale networked system composed of a set of components or functions, each of which is called a service. A problem to construct behavioral models of services from given global interaction specifications, called choreography, is known as the choreography realization problem. The constructed model is still an intermediate model in the process of system developments; the model will be corrected, modified, and enhanced further by designers. Therefore, we also have to consider readability of the constructed model. In this paper, we proposed a method to construct state machine models from choreographies described by a set of communication diagrams using Petri nets. The proposed method will try to use the composite states and the orthogonal regions of UML state machines for the readability.     

Analysis of railway stations by means of interval timed coloured Petri nets

In this paperinterval timed coloured Petri nets ((van der Aalst, 1993)) are used to model and analyse railway stations. We will show that this approach can be used to evaluate both station operating schedules and the infrastructure of a station.An interval timed coloured Petri net (ITCPN) is a coloured Petri net extended with time; time is in tokens and transitions determine a delay for each produced token. This delay is specified by an upper and lower bound, i.e. an interval. The ITCPN model allows for the modelling of the dynamic behaviour of large and complex systems, without loosing the possibility of formal analysis. In addition to the existing analysis techniques for coloured Petri nets, we use a new analysis method to analyse the temporal behaviour of the net. This method constructs a reduced reachability graph and exploits the fact that delays are described by an interval. We will also discuss other (Petri net based) methods that can be used to analyse railway stations.By order of and in co-operation with the Dutch Railway Company (NS), Department of Traffic Development.     

Parallel program design using high-level Petri nets

Petri nets are proposed as a general-purpose design and modelling tool for parallel programs. The advantages of Petri nets for this purpose are discussed, and a solution to the Dining Philosophers problem is developed using simple Place-Transition nets. The limitations of Place-Transition nets are described, and the Dining Philosophers problem is used to illustrate how Coloured Petri nets can overcome these limitations. A more complex example of a Coloured Petri net is then given, and it is shown how a collection of processes in the Occam programming language can be developed directly from the properties of the net. Another Petri net model of a simple process farm is given, and a solution is developed in Parallel C: this further highlights the suitability of Petri nets as a design tool for parallel programs.