Catálogo de publicaciones - libros

This paper is a survey of the Stochastic Well-formed Net (SWN) formalism evolution, in particular it discusses the expressiveness of the formalism in terms of ease of use from the modeler point of view, and briefly presents the main results that can be found in the literature about efficient (state space based) analysis of SWN models. Software tools supporting SWN design and analysis are also mentioned in the paper. The goal of the paper is not to present in details the formalism nor the analysis algorithms, but rather to recall the achieved results and to highlight open problems and possible directions for new developments in this research area.

A Craig interpolant [1] for a mutually inconsistent pair of formulas (A,B) is a formula that is (1) implied by A, (2) inconsistent with B, and (3) expressed over the common variables of A and B. It is known that a Craig interpolant can be efficiently derived from a refutation of A ∧ B , for certain theories and proof systems. For example, interpolants can be derived from resolution proofs in propositional logic, and for systems of linear inequalities over the reals [6,4]. These methods have been recently extended to combine linear inequalities with uninterpreted function symbols, and to deal with integer models [5]. One key aspect of these procedures is that the yield quantifier-free interpolants when the premises A and B are quantifier-free.

Clashing security policies leads to vulnerabilities. Violating security policies leads to vulnerabilities. A system today operates in the context of a multitude of security policies, often one per application, one per process, one per user. The more security policies that have to be simultaneously satisfied, the more likely the possibility of a clash or violation, and hence the more vulnerable our system is to attack. Moreover, over time a system’s security policies will change. These changes occur at small-scale time steps, e.g., using setuid to temporarily grant a process additional access rights; and at large-scale time steps, e.g., when a user changes his browser’s security settings. We address the challenge of determining when a system is in a consistent state in the presence of diverse, numerous, and dynamic interacting security policies.

State explosion is a fundamental problem in the analysis and synthesis of discrete event systems. Continuous Petri nets can be seen as a relaxation of discrete models allowing more efficient (in some cases polynomial time) analysis and synthesis algorithms. Nevertheless computational costs can be reduced at the expense of the analyzability of some properties. Even more, some net systems do not allow any kind of continuization. The present work first considers these aspects and some of the alternative formalisms usable for continuous relaxations of discrete systems. Particular emphasis is done later on the presentation of some results concerning performance evaluation, parametric design and marking (i.e., state) observation and control. Even if a significant amount of results are available today for continuous net systems, many essential issues are still not solved. A list of some of these are given in the introduction as an invitation to work on them.

The topic of process mining has attracted the attention of both researchers and tool vendors in the Business Process Management (BPM) space. The goal of process mining is to discover process models from event logs, i.e., events logged by some information system are used to extract information about activities and their causal relations. Several algorithms have been proposed for process mining. Many of these algorithms cannot deal with concurrency. Other typical problems are the presence of duplicate activities, hidden activities, non-free-choice constructs, etc. In addition, real-life logs contain noise (e.g., exceptions or incorrectly logged events) and are typically incomplete (i.e., the event logs contain only a fragment of all possible behaviors). To tackle these problems we propose a completely new approach based on genetic algorithms. As can be expected, a genetic approach is able to deal with noise and incompleteness. However, it is not easy to represent processes properly in a genetic setting. In this paper, we show a genetic process mining approach using the so-called causal matrix as a representation for individuals. We elaborate on the relation between Petri nets and this representation and show that genetic algorithms can be used to discover Petri net models from event logs.

We study probabilistic safe Petri nets , a probabilistic extension of safe Petri nets interpreted under the true-concurrent semantics. In particular, the likelihood of processes is defined on partial orders, not on firing sequences. We focus on memoryless probabilistic nets: we give a definition for such systems, that we call Markov nets, and we study their properties. We show that several tools from Markov chains theory can be adapted to this true-concurrent framework. In particular, we introduce stopping operators that generalize stopping times, in a more convenient fashion than other extensions previously proposed. A Strong Markov Property holds in the concurrency framework. We show that the Concurrent Strong Markov property is the key ingredient for studying the dynamics of Markov nets. In particular we introduce some elements of a recurrence theory for nets, through the study of renewal operators. Due to the concurrency properties of Petri nets, Markov nets have global and local renewal operators, whereas both coincide for sequential systems.

This paper deals with the structure theory of Petri nets. We define the class of P/T systems namely K-systems for which the equivalence between controlled-siphon property (cs property), deadlock freeness, and liveness holds. Using the new structural notions of ordered transitions and root places, we revisit the non liveness characterization of P/T systems satisfying the cs property and we define by syntactical manner new and more expressive subclasses of K-systems where the interplay between conflict and synchronization is relaxed.

We give a method to compute the throughput in a timed live and bounded free-choice Petri net under a total allocation ( i.e. a 0-1 routing). We also characterize and compute the conflict-solving policies that achieve the smallest throughput in the special case of a 1-bounded net. They do not correspond to total allocations, but still have a small period.

This paper presents a framework to decompose a single GSPN model into a set of small interacting models. This decomposition technique can be applied to any GSPN model with a finite set of tangible markings and a generalized tensor algebra (Kronecker) representation can be produced automatically. The numerical impact of all the possible decompositions obtained by our technique is discussed. To do so we draw the comparison of the results for some practical examples. Finally, we present all the computational gains achieved by our technique, as well as the future extensions of this concept for other structured formalisms.

Current modeling techniques are not well equipped to design dynamic software architectures. In this work we present the basic concepts for a dynamic architecture modeling using nets-within-nets. Nets-within-nets represent a powerful formalism that allows active elements, i.e. nets, to be nested in arbitrary and dynamically changeable hierarchies. Applying the concepts from nets-within-nets, therefore, allows us to model complex dynamic system architectures in a simple way, which enables us to design the system at different levels of abstractions using refinements of net models. Additionally to the conceptual modeling of such architecture, we provide a practical example where the concept has been successfully applied in the development of the latest release of Renew (Version 2 of the multi-formalism Petri net IDE). The overall monolithic architecture has been exchanged with a system that is divided into a plug-in management system and plug-in’s that provide functionality for the users. By combining plug-ins the system can be adapted to the users’ needs. Through the introduction of the Petri net concepts, the new architecture is now – at runtime – dynamically extensible by registering plug-ins with the management system. The introduced architecture is applicable for any kind of architecture but most suitable for applications with dynamic structure.