Unfoldings are a well known partial-order semantics of P/T Petri nets that can be applied to various model checking or verification problems. For high-level Petri nets, the so-called symbolic unfolding generalizes this notion. A complete finite prefix of a P/T Petri net’s unfolding contains all information to verify, e.g., reachability of markings. We unite these two concepts and define complete finite prefixes of the symbolic unfolding of high-level Petri nets. For a class of safe high-level Petri nets, we generalize the well-known algorithm by Esparza et al. for constructing small such prefixes. We evaluate this extended algorithm through a prototype implementation on four novel benchmark families. Additionally, we identify a more general class of nets with infinitely many reachable markings, for which an approach with an adapted cut-off criterion extends the complete prefix methodology, in the sense that the original algorithm cannot be applied to the P/T net represented by a high-level net.

Unfoldings are a well known partial-order semantics of P/T Petri nets that can be applied to various model checking or verification problems. For high-level Petri nets, the so-called symbolic unfolding generalizes this notion. A complete finite prefix of a P/T Petri net's unfolding contains all information to verify, e.g., reachability of markings. We unite these two concepts and define complete finite prefixes of the symbolic unfolding of high-level Petri nets. For a class of safe high-level Petri nets, we generalize the well-known algorithm by Esparza et al. for constructing small such prefixes. We evaluate this extended algorithm through a prototype implementation on four novel benchmark families. Additionally, we identify a more general class of nets with infinitely many reachable markings, for which an approach with an adapted cut-off criterion extends the complete prefix methodology, in the sense that the original algorithm cannot be applied to the P/T net represented by a high-level net. Comment: This is a revised and extended version of "Nick W\"urdemann, Thomas Chatain, Stefan Haar: Taking Complete Finite Prefixes to High Level, Symbolically. Petri Nets 2023: 123-144"

The Program Committee selected 23 out of 41 papers submitted to Petri Nets 2020 by authors from 19 different countries.Each paper was reviewed by three reviewers.After the conference, five papers were distinguished by the Program Committee members.The authors were invited to revise and extend their conference papers for this special issue, and the extended submissions have been reviewed in a separate reviewing process, to meet the standards of Fundamenta Informaticae.Three of these works address the synthesis problem, albeit from rather different points of views (complexity, compositionality and synthesis in a timed context).New results on the complexity and expressiveness of Recursive Petri nets and an in-depth investigation of the intricate connection between sequential and concurrent semantics in Petri nets reversibility, complete this special issue.

A central task in partially observed controllable system is to detect or prevent the occurrence of certain events called faults. Systems for which one can design a controller avoiding the faults are called actively safe. Otherwise, one may require that a fault is eventually detected, which is the task of diagnosis. Systems for which one can design a controller detecting the faults are called actively diagnosable. An intermediate requirement is prediction, which consists in determining that a fault will occur whatever the future behaviour of the system. When a system is not predictable, one may be interested in designing a controller to make it so. Here we study the latter problem, called active prediction, and its associated property, active predictability. In other words, we investigate how to determine whether or not a system enjoys the active predictability property, i.e., there exists an active predictor for the system. Our contributions are threefold. From a semantical point of view, we refine the notion of predictability by adding two quantitative requirements: the minimal and maximal delay before the occurence of the fault, and we characterize the requirements fulfilled by a controller that performs predictions. Then we show that active predictability is EXPTIME-complete where the upper bound is obtained via a game-based approach. Finally we establish that active predictability is equivalent to active safety when the maximal delay is beyond a threshold depending on the size of the system, and we show that this threshold is accurate by exhibiting a family of systems fulfilling active predictability but not active safety.

Cellular reprogramming, a technique that opens huge opportunities in modern and regenerative medicine, heavily relies on identifying key genes to perturb. Most of the existing computational methods for controlling which attractor (steady state) the cell will reach focus on finding mutations to apply to the initial state. However, it has been shown, and is proved in this article, that waiting between perturbations so that the update dynamics of the system prepares the ground, allows for new reprogramming strategies. To identify such sequential perturbations, we consider a qualitative model of regulatory networks, and rely on Binary Decision Diagrams to model their dynamics and the putative perturbations. Our method establishes a set identification of sequential perturbations, whether permanent (mutations) or only temporary, to achieve the existential or inevitable reachability of an arbitrary state of the system. We apply an implementation for temporary perturbations on models from the literature, illustrating that we are able to derive sequential perturbations to achieve trans-differentiation.

We define HyPOL, a local hyper logic for partial order models, expressing properties of sets of runs. These properties depict shapes of causal dependencies in sets of partially ordered executions, with similarity relations defined as isomorphisms of past observations. Unsurprisingly, since comparison of projections are included, satisfiability of this logic is undecidable. We then address model checking of HyPOL and show that, already for safe Petri nets, the problem is undecidable. Fortunately, sensible restrictions of observations and nets allow us to bring back model checking of HyPOL to a decidable problem, namely model checking of MSO on graphs of bounded treewidth.

Diagnosability and opacity are two well-studied problems in discrete-event systems. We revisit these two problems with respect to expressiveness and complexity issues. We first relate different notions of diagnosability and opacity. We consider in particular fairness issues and extend the definition of Germanos et al. [ACM TECS, 2015] of weakly fair diagnosability for safe Petri nets to general Petri nets and to opacity questions. Second, we provide a global picture of complexity results for the verification of diagnosability and opacity. We show that diagnosability is NL-complete for finite state systems, PSPACE-complete for safe convergent Petri nets (even with fairness), and EXPSPACE-complete for general Petri nets without fairness, while non diagnosability is inter-reducible with reachability when fault events are not weakly fair. Opacity is ESPACE-complete for safe Petri nets (even with fairness) and undecidable for general Petri nets already without fairness.

Diagnosis is the task of detecting fault occurrences in a partially observed system. Depending on the possible observations, a discrete-event system may be diagnosable or not. Active diagnosis aims at controlling the system to render it diagnosable. Past research has proposed solutions for this problem, but their complexity remains to be improved. Here, we solve the decision and synthesis problems for active diagnosability, proving that (1) our procedures are optimal with respect to computational complexity, and (2) the memory required for our diagnoser is minimal. We then study the delay between a fault occurrence and its detection by the diagnoser. We construct a memory-optimal diagnoser whose delay is at most twice the minimal delay, whereas the memory required to achieve optimal delay may be highly greater. We also provide a solution for parametrized active diagnosis, where we automatically construct the most permissive controller respecting a given delay.

No abstract available.

We enrich spatial constraint systems with operators to specify information and processes moving from a space to another. We shall refer to these news structures as spatial constraint systems with extrusion. We shall investigate the properties of this new family of constraint systems and illustrate their applications. From a computational point of view the new operators provide for process/information extrusion, a central concept in formalisms for mobile communication. From an epistemic point of view extrusion corresponds to a notion we shall call utterance; a piece of information that an agent communicates to others but that may be inconsistent with the agent's beliefs. Utterances can then be used to express instances of epistemic notions, which are common place in social media, such as hoaxes or intentional lies. Spatial constraint systems with extrusion can be seen as complete Heyting algebras equipped with maps to account for spatial and epistemic specifications.

In partially observed Petri nets, diagnosis is the task of detecting whether the given sequence of observed labels indicates that some unobservable fault has occurred. Diagnosability is an associated property of the Petri net, stating that in any possible execution, an occurrence of a fault can eventually be diagnosed. In this article, we consider diagnosability under the weak fairness (WF) assumption, which intuitively states that no transition from a given set can stay enabled forever—it must eventually either fire or be disabled. We show that a previous approach to WF-diagnosability in the literature has a major flaw and present a corrected notion. Moreover, we present an efficient method for verifying WF-diagnosability based on a reduction to LTL-X model checking. An important advantage of this method is that the LTL-X formula is fixed—in particular, the WF assumption does not have to be expressed as a part of it (which would make the formula length proportional to the size of the specification), but rather the ability of existing model checkers to handle weak fairness directly is exploited.

The semantics of concurrent processes can be defined in terms of partially ordered sets. Occurrence nets, which belong to the family of Petri nets, model concurrent processes as partially ordered sets of occurrences of local states and local events. On the basis of the associated concurrency relation, a closure operator can be defined, giving rise to a lattice of closed sets. Extending previous results along this line, the present paper studies occurrence nets with forward conflicts, modelling families of processes. It is shown that the lattice of closed sets is orthomodular, and the relations between closed sets and some particular substructures of an occurrence net are studied. In particular, the paper deals with runs, modelling concurrent histories, and trails, corresponding to possible histories of sequential components. A second closure operator is then defined by means of an iterative procedure. The corresponding closed sets, here called ‘dynamically closed’, are shown to form a complete lattice, which in general is not orthocomplemented. Finally, it is shown that, if an occurrence net satisfies a property called B-density, which essentially says that any antichain meets any trail, then the two notions of closed set coincide, and they form a complete, algebraic orthomodular lattice.

SUMMARY We propose a theoretical testing framework and a test generation algorithm for concurrent systems specified with true‐concurrency models, such as Petri nets or networks of automata. The semantic model of computation of such formalisms is labelled event structures, which allow to represent concurrency explicitly. We introduce the notions of strong and weak concurrency: strongly concurrent events must be concurrent in the implementation, while weakly concurrent ones may eventually be ordered. The ioco type conformance relations for sequential systems rely on the observation of sequences of actions and blockings; thus, they are not capable of capturing and exploiting concurrency of non‐sequential behaviours. We propose an extension of ioco for labelled event structures, named co‐ioco, allowing to deal with strong and weak concurrency. We extend the notions of test cases and test execution to labelled event structures and give a test generation algorithm building a complete test suite for co‐ioco. Copyright © 2014 John Wiley & Sons, Ltd.

Occurrence nets are a well known partial order model for the concurrent behavior of Petri nets. The causality and conflict relations between events, which are explicitly represented in occurrence nets, induce logical dependencies between event occurrences: the occurrence of an event e in a run implies that all its causal predecessors also occur, and that no event in conflict with e occurs. But these structural relations do not express all the logical dependencies between event occurrences in maximal runs: in particular, the occurrence of e in any maximal run may imply the occurrence of another event that is not a causal predecessor of e, in that run. The reveals relation has been introduced to express this dependency between two events. Here we generalize the reveals relation to express more general dependencies, involving more than two events, and we introduce ERL logic to express them as boolean formulas. Finally we answer the synthesis problem that arises: given an ERL formula �, is there an occurrence net 𝒩 such that � describes exactly the dependencies between the events of 𝒩?

Real-time distributed systems may be modeled in different formalisms such as time Petri nets (TPN) and networks of timed automata (NTA). This paper focuses on translating a 1-bounded TPN into an NTA and considers an equivalence which takes the distribution of actions into account. This translation is extensible to bounded TPNs. We first use S-invariants to decompose the net into components that give the structure of the automata, then we add clocks to provide the timing information. Although we have to use an extended syntax in the timed automata, this is a novel approach since the other transformations and comparisons of these models did not consider the preservation of concurrency.

International audience

Service level agreements (SLAs), or contracts, have an important role in web services. They define the obligations and rights between the provider of a web service and its client, about the function and the Quality of the service (QoS). For composite services like orchestrations, contracts are deduced by a process called QoS contract composition, based on contracts established between the orchestration and the called web services. Contracts are typically stated as hard guarantees (e.g., response time always less than 5 msec). Using hard bounds is not realistic, however, and more statistical approaches are needed. In this paper we propose using soft probabilistic contracts instead, which consist of a probability distribution for the considered QoS parameter—in this paper, we focus on timing. We show how to compose such contracts, to yield a global probabilistic contract for the orchestration. Our approach is implemented by the TOrQuE tool. Experiments on TOrQuE show that overly pessimistic contracts can be avoided and significant room for safe overbooking exists. An essential component of SLA management is then the continuous monitoring of the performance of called web services, to check for violations of the SLA. We propose a statistical technique for run-time monitoring of soft contracts.

The way Internet is used changes: demand grows for critical services that cross several provider networks; guaranteeing a required end-to-end quality of service (QoS) across several networks becomes a challenge. Some critical services (e.g. video-conference, VPN etc.) can not be satisfied in a best effort fashion. The use of QoS contracts (service level agreements, SLAs) is effective for management of such services. However, the problem of meeting end-to-end QoS requirement remains: no centralized entity can compute overall QoS for chains of contracts, and a fortiori, such contract chains can not be optimized centrally. Thus, the following problem has to be solved: given an end- to-end QoS request and collections of available SLAs on each participating domain, establish an end-to-end contract committing a chain of providers and giving optimal service under most reliable guarantees available.

Web services orchestrations and choreographies require establishing quality of service (QoS) contracts with the user. This is achieved by performing QoS composition, based on contracts established between the orchestration and the called Web services. These contracts are typically stated in the form of hard guarantees (e.g., response time always less than 5 msec). In this paper we propose using soft contracts instead. Soft contracts are characterized by means of probability distributions for QoS parameters. We show how to compose such contracts, to yield a global contract (probabilistic) for the orchestration. Our approach is implemented by the TOrQuE tool. Experiments on TOrQuE show that overly pessimistic contracts can be avoided and significant room for safe overbooking exists.

Multi-media services and other critical multi-site services (e.g. VPN) are becoming mainstream, and require a guaranteed Quality of Service (QoS). Services need to be established across several domains, often to connect multi-domain end-users. Thus, provisioning and control of end-to-end QoS requirements arises as one of the main challenges in X-domain management. While the use of QoS contracts (Service Level Agreements, SLAs) is crucial, the problem of QoS guarantees goes beyond the scope of contracts between one server and one client. End-to-end QoS contracts are subject to cumulation effects that must be taken into account. Moreover, several paths of contracts may satisfy the user's QoS requirements. While our previous work studied negotiation of end-to-end QoS contracts for single service requests, we turn here to pipes that handle large numbers of requests, allocating from a variety of contract chains between a fixed source and a fixed target domain. For incoming requests, a pipe selects from a pre-established set of contract chains, rather then launching a new negotiation. This paper studies the optimization and constraint resolution problems arising in pipe negotiation.

Web services orchestrations require a firm mathematical basis for their development, regarding both their functional and QoS characteristics. We provide such a basis in the form of a model based on colored Petri net systems. Our approach allows evaluating end-to-end QoS of the orchestration with the help of the QoS of the called sites.

We consider query optimization techniques for data intensive P2P applications. We show how to adapt an old technique from deductive databases, namely Query-Sub-Query (QSQ), to a setting where autonomous and distributed peers share large volumes of interelated data.We illustrate the technique with an important telecommunication problem, the diagnosis of distributed telecom systems. We show that (i) the problem can be modeled using Datalog programs, and (ii) it can benefit from the large battery of optimization techniques developed for Datalog. In particular, we show that a simple generic use of the extension of QSQ achieves an optimization as good as that previously provided by dedicated diagnosis algorithms. Furthermore, we show that it allows solving efficiently a much larger class of system analysis problems.

This paper investigates Occurrence (Petri) Nets on two levels: their structural theory and their interpretation in branching unfolding semantics of Petri Net systems. The key issue is the decomposition of occurrence nets into substructures given by the node relations associated with causal ordering, concurrency, and conflict. In addition to lines and cuts, which have long been studied in the context of causal nets ([1]), we introduce and study branches, trails, choices, and alternatives. All finite systems will be shown to satisfy certain density properties, i.e. non-empty intersections of substructures as above. On the semantic level, we introduce partial order logics to be interpreted on two different kind of frames, given by substructures of occurrence nets: on the frame of cuts, the CTL * type logics BFC and BLC, and the “non-branching” logic LLC, taylored to the frame given by the lattice of choices.