Petri net synthesis consists in deciding for a given transition system $A$ whether there exists a Petri net $N$ whose reachability graph is isomorphic to $A$. Several works examined the synthesis of Petri net subclasses that restrict, for every place $p$ of the net, the cardinality of its preset or of its postset or both in advance by small natural numbers $\varrho$ and $\kappa$, respectively, such as for example (weighted) marked graphs, (weighted) T-systems and choice-free nets. In this paper, we study the synthesis aiming at Petri nets which have such restricted place environments, from the viewpoint of classical and parameterized complexity: We first show that, for any fixed natural numbers $\varrho$ and $\kappa$, deciding whether for a given transition system $A$ there is a Petri net $N$ such that (1) its reachability graph is isomorphic to $A$ and (2) for every place $p$ of $N$ the preset of $p$ has at most $\varrho$ and the postset of $p$ has at most $\kappa$ elements is doable in polynomial time. Secondly, we introduce a modified version of the problem, namely Environment Restricted Synthesis (ERS, for short), where $\varrho$ and $\kappa$ are part of the input, and show that ERS is NP-complete, regardless whether the sought net is impure or pure. In case of the impure nets, our methods also imply that ERS parameterized by $\varrho+\kappa$ is $W[2]$-hard.

In Petri net synthesis we ask whether a given transition system A can be implemented by a Petri net N. Depending on the level of accuracy, there are three ways how N can implement A: an embedding, the least accurate implementation, preserves only the diversity of states of A; a language simulation already preserves exactly the language of A; a realization, the most accurate implementation, realizes the behavior of A exactly. However, whatever the sought implementation, a corresponding net does not always exist. In this case, it was suggested to modify the input behavior – of course as little as possible. Since transition systems consist of states, events and edges, these components appear as a natural choice for modifications. In this paper we show that the task of converting an unimplementable transition system into an implementable one by removing as few states or events or edges as possible is NP-complete –regardless of what type of implementation we are aiming for; we also show that the corresponding parameterized problems are W[2]-hard, where the number of removed components is considered as the parameter; finally, we show there is no c-approximation algorithm (with a polynomial running time) for neither of these problems, for every constant c ≥ 1.

Let us consider some class of (Petri) nets. The corresponding Synthesis problem consists in deciding whether a given labeled transition system (TS) A can be implemented by a net N of that class. In case of a negative decision, it may be possible to convert A into an implementable TS B by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges/states/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if the considered class corresponds to so-called flip-flop nets or some flip-flop net derivatives.

In order to speed up the synthesis of Petri nets from labelled transition systems, a divide and conquer strategy consists in defining decompositions of labelled transition systems, such that each component is synthesisable iff so is the original system. Then corresponding Petri Net composition operators are searched to combine the solutions of the various components into a solution of the original system. The paper presents two such techniques, which may be combined: products and articulations. They may also be used to structure transition systems, and to analyse the performance of synthesis techniques when applied to such structures.

We formalise and study multi-agent timed models MAPTs (Multi-Agent with Periodic timed Tasks), where each agent is associated with a regular timed schema upon which all possible actions of the agent rely. MAPTs allow for an accelerated semantics and a layered structure of the state space, so that it is possible to explore the latter dynamically and use heuristics to greatly reduce the computation time needed to address reachability problems. We use an available tool for the Petri net implementation of MAPTs, to explore the state space of autonomous vehicle systems. Then, we compare this exploration with timed automata-based approaches in terms of expressiveness of available queries and computation time.

When a Petri net is synthesised from a labelled transition system, it is frequently desirable that certain additional constraints are fulfilled. For example, in circuit design, one is often interested in constructing safe Petri nets. Targeting such subclasses of Petri nets is not necessarily computationally more efficient than targeting the whole class. For example, targeting safe nets is known to be NP-complete while targeting the full class of place/transition nets is polynomial, in the size of the transition system. In this paper, several classes of Petri nets are examined, and their suitability for being targeted through efficient synthesis from labelled transition systems is studied and assessed. The focus is on choice-free Petri nets and some of their subclasses. It is described how they can be synthesised efficiently from persistent transition systems, summarising and streamlining in tutorial style some of the authors’ and their groups’ work over the past few years.

Numerous real-world systems can be modeled with Petri nets, which allow a combination of concurrency with synchronizations and conflicts. To alleviate the difficulty of checking their behaviour, a common approach consists in studying specific subclasses. In the converse problem of Petri net synthesis, a Petri net of some subclass has to be constructed efficiently from a given specification, typically from a labelled transition system (lts) describing the behaviour of the desired net. In this paper, we focus on a notorious subclass of persistent Petri nets, the weighted marked graphs (WMGs), also called generalised (or weighted) event (or marked) graphs or weighted T-nets. In such nets, edges have multiplicities (weights) and each place has at most one ingoing and one outgoing transition. Although extensively studied in previous works and benefiting from strong results, both their analysis and synthesis can be further investigated. We provide new behavioural properties of WMGs expressed on their reachability graph, notably backward persistence and strong similarities between any two sequences sharing the same starting state and the same destination state. Besides, we design a general synthesis procedure aiming at the WMG class. Finally, when no solution to the synthesis problem exists, i.e., when the given lts is not WMG-solvable, we show how to construct a WMG whose reachability graph is a minimal over-approximation of the given lts.

Liveness, (non-)deadlockability and reversibility are behavioral properties of Petri nets that are fundamental for many real-world systems. Such properties are often required to be monotonic, meaning preserved upon any increase of the marking. However, their checking is intractable in general and t heir monotonicity is not always satisfied. To simplify the analysis of these features, structural approaches have been fruitfully exploited in particular subclasses of Petri nets, deriving the behavior from the underlying graph and the initial marking only, often in polynomial time. In this paper, we further develop these efficient structural methods to analyze deadlockability, liveness, reversibility and their monotonicity in weighted Petri nets. We focus on the join-free subclass, which forbids synchronizations, and on the homogeneous asymmetric-choice subclass, which allows conflicts and synchronizations in a restricted fashion. For the join-free nets, we provide several structural conditions for checking liveness, (non-)deadlockability, reversibility and their monotonicity. Some of these methods operate in polynomial time. Furthermore, in this class, we show that liveness, non-deadlockability and reversibility, taken together or separately, are not always monotonic, even under the assumptions of structural boundedness and structural liveness. These facts delineate more sharply the frontier between monotonicity and non-monotonicity of the behavior in weighted Petri nets, present already in the join-free subclass. In addition, we use part of this new material to correct a flaw in the proof of a previous characterization of monotonic liveness and boundedness for homogeneous asymmetric-choice nets, published in 2004 and left unnoticed.

In this paper, we shall examine properties of labelled transition systems which are motivated by system synthesis. Most of them are necessary conditions for synthesis by Petri nets to be successful. They can be checked in a pre-synthesis phase, allowing the immediate rejection of transition systems not satisfying them as non-synthesisable. The order of checking such conditions plays an important role in pre-synthesis optimisation. It is particularly desirable to know which conditions are implied by others, especially if the latter can be machine-verified more simply than the former. The purpose of this paper is to describe some mathematical results exhibiting a number of such implications. Two properties called strong cycle-consistency and full backward determinism, respectively, are particularly hard to check. They are generalised counterparts of the marking equation of Petri net theory. We show that under some circumstances, they may be deduced from other properties which are easier to check. Amongst these other properties, the prime cycle property plays a particularly important role, not just because it is strong enough to imply others, but also because it is interesting to be checked on its own, if synthesis is targetted towards choice-free Petri nets.

This special issue is dedicated to papers selected from the 36th International Conference on Application and Theory of Petri Nets and Other Models of Concurrency (Petri Nets 2015), which was held June 21-26, 2015 in Brussels, Belgium.

This paper describes a synthesis algorithm tailored to the construction of choice-free Petri nets from finite persistent transition systems. With this goal in mind, a minimised set of simplified systems of linear inequalities is distilled from a general region-theoretic approach, leading to algorithmic improvements as well as to a partial characterisation of the class of persistent transition systems that have a choice-free Petri net realisation.

This paper presents a dedicated Petri net synthesis algorithm for the case that a transition system is finite, live, and persistent. In particular, the paper delineates exactly when and how a structurally persistent net may be constructed, by crystallising, out of a general region-theoretic approach, a minimised set of simplified systems of linear inequalities. This extends previous results where reversibility, instead of liveness, played an important role.

Mixed reality systems overlay real data with virtual information in order to assist users in their current task, they are used in many fields (surgery, maintenance, entertainment). Such systems generally combine several hardware components operating at different time scales, and software that has to cope with these timing constraints. MIRELA, for Mixed Reality Language, is a framework aimed at modelling, analysing and implementing systems composed of sensors, processing units, shared memories and rendering loops, communicating in a well-defined manner and submitted to timing constraints. The paper describes how harmful software behaviour, which may result in possible hardware deterioration or revert the system's primary goal from user assistance to user impediment, may be detected such as (global and local) deadlocks or starvation features. This also includes a study of temporal properties resulting in a finer understanding of the software timing behaviour, in order to fix it if needed.

We present a Petri net interpretation of the pi-graphs - a graphical variant of the picalculus where recursion and replication are replaced by iteration. The concise and syntax-driven translation can be used to reason in Petri net terms about open re

Abstract We propose a finite structural translation of possibly recursive π -calculus terms into Petri nets. This is achieved by using high-level nets together with an equivalence on markings in order to model entering into recursive calls, which do not need to be guarded. We view a computing system as consisting of a main program ( π -calculus term) together with procedure declarations (recursive definitions of π -calculus identifiers). The control structure of these components is represented using disjoint high-level Petri nets, one for the main program and one for each of the procedure declarations. The program is executed once, while each procedure can be invoked several times (even concurrently), each such invocation being uniquely identified by structured tokens which correspond to the sequence of recursive calls along the execution path leading to that invocation.

BACKGROUND: An appropriate choice of the modeling formalism from the broad range of existing ones may be crucial for efficiently describing and analyzing biological systems. RESULTS: We propose a new unifying and incremental formalism for the representation and modeling of biological interaction networks. This formalism allows automated translations into other formalisms, thus enabling a thorough study of the dynamic properties of a biological system. As a first illustration, we propose a translation into the R. Thomas' multivalued logical formalism which provides a possible semantics; a methodology for constructing such models is presented on a classical benchmark: the lambda phage genetic switch. We also show how to extract from our model a classical ODE description of the dynamics of a system. CONCLUSION: This approach provides an additional level of description between the biological and mathematical ones. It yields, on the one hand, a knowledge expression in a form which is intuitive for biologists and, on the other hand, its representation in a formal and structured way.

In this paper we study the problem of scheduling hard real-time periodic task sets with a dynamic and preemptive scheduler. We will focus on the response time notion, its interest and its effective computation for the deadline driven scheduler. We pr

Abstract In a basic agent calculus, equality often links the agents which provide the same external behaviour in any context. Since the universe of agents and the universe of contexts depend on the used action set, equality depends a priori on this set of actions. We show here that if we select from the universe of agents, two agents which are equal, they are also equal if we extend the universe of actions (and consequently if we extend the universe of agents and contexts).

From a critical examination of the class of strategies preventing individual starvation with global control, introduced by E. W. Dijkstra, another class of strategies is introduced, which is simpler to implement and whose behaviour has a straightforward interpretation. Both classes are in fact distinct sub-classes of a more general family of strategies.

When parallel processes are linked in producer-consumer pairs and share a finite buffer where every portion is accessible to each process, it appears that a slow consumer may considerably delay the entire system. Using conditional critical sections, Dijkstra has proposed to reserve for each producer-consumer pair the adequate number of portions for a normal working and to dedicate the rest of the buffer to absorb the production peaks of the various pairs. L. W. Cooprider et al. then developed solutions which avoid systematic inspection and only use the now classical synchronisation primitives P and V. The present paper is devoted to the elaboration of solutions which improve parallelism and, when useful, discharge processes of administrative tasks. We have used and compared four synchronising methods to this aim: conditional critical sections, semaphores, path expressions and monitors.