Wyniki wyszukiwania - BazTech

1

Synthesis of Pure and Impure Petri nets with Restricted Place-environments : Complexity Issues

Devillers Raymond, Tredup Ronny

Fundamenta Informaticae

|

2022

|

vol. 187 nr 2-4

139--165

EN

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̺ and κ, 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̺ and κ, 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̺ and the postset of p has at most κ elements is doable in polynomial time. Secondly, we introduce a modified version of the problem, namely ENVIRONMENT RESTRICTED SYNTHESIS (ERS, for short), where̺ and κ 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̺ + κ is W [2]-hard.

2

Some Basic Techniques allowing Petri Net Synthesis: Complexity and Algorithmic Issues

Devillers Raymond, Tredup Ronny

Fundamenta Informaticae

|

2022

|

vol. 187 nr 2-4

167--196

EN

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 implemen- tation, 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.

3

On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets

Devillers Raymond, Tredup Ronny

Fundamenta Informaticae

|

2022

|

Vol. 189, nr 3-4

261--296

EN

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.

4

Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis

Devillers Raymond

Fundamenta Informaticae

|

2021

|

Vol. 183, nr 1-2

1--31

EN

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.

5

Target-oriented Petri Net Synthesis

Best Eike, Devillers Raymond, Erofeev Evgeny, Wimmel Harro

Fundamenta Informaticae

|

2020

|

Vol. 175, nr 1-4

97--122

EN

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.

6

Dynamic Exploration of Multi-agent Systems with Periodic Timed Tasks

Arcile Johan, Devillers Raymond, Klaudel Hanna

Fundamenta Informaticae

|

2020

|

Vol. 175, nr 1-4

59--95

EN

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.

7

Analysis and Synthesis of Weighted Marked Graph Petri Nets : Exact and Approximate Methods

Devillers Raymond, Hujsa Thomas

Fundamenta Informaticae

|

2019

|

Vol. 169, nr 1-2

1--30

EN

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.