Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

2 2022

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Formal Languages and Automata Theory

Sortuj według:

Ogranicz wyniki do:

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

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.

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

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.