Zur Komplexität der Synthese von Petri-Netzen

Ronny Tredup

doi:10.18453/rosdok_id00003375

Ronny Tredup

Zur Komplexität der Synthese von Petri-Netzen

Universität Rostock, 2021

https://doi.org/10.18453/rosdok_id00003375

Abstract: Petri-Netz-Synthese fragt für ein reguläres Verhalten, das als Transitionssystem A gegeben ist, ob es ein Petri-Netz (einer bestimmten Klasse) gibt, das A implementiert. Diese Arbeit untersucht Varianten dieses Entscheidungsproblems für verschiedene Implementierungen und eine Vielzahl von Petri-Netz-Klassen aus Sicht der klassischen und der parametrisierten Komplexität. Ebenso wird die Komplexität der Modifikations-Techniken Neubeschriftung sowie Kanten-, Ereignis- und Zustandslöschung untersucht, die darauf abzielen, nicht-implememtierbare Transitionssysteme implementierbar zu machen.

Dissertation Freier Zugang

Titel:

Zur Komplexität der Synthese von Petri-Netzen

Beteiligte Personen:

Ronny Tredup[VerfasserIn]
	1246043041
Karsten Wolf[AkademischeR BetreuerIn]
	124773052
	Universität Rostock
Robert Lorenz[AkademischeR BetreuerIn]
	Universität Augsburg

Beteiligte Körperschaften:

Universität Rostock[Grad-verleihende Institution]
	38329-6
Universität Rostock, Fakultät für Informatik und Elektrotechnik[Grad-verleihende Institution]
	10085032-7

Zusammenfassung:

Petri-Netz-Synthese fragt für ein reguläres Verhalten, das als Transitionssystem A gegeben ist, ob es ein Petri-Netz (einer bestimmten Klasse) gibt, das A implementiert. Diese Arbeit untersucht Varianten dieses Entscheidungsproblems für verschiedene Implementierungen und eine Vielzahl von Petri-Netz-Klassen aus Sicht der klassischen und der parametrisierten Komplexität. Ebenso wird die Komplexität der Modifikations-Techniken Neubeschriftung sowie Kanten-, Ereignis- und Zustandslöschung untersucht, die darauf abzielen, nicht-implememtierbare Transitionssysteme implementierbar zu machen. [Deutsch]

Petri net synthesis asks, for a regular behavior given as a transition system A, whether there exists a Petri net (of a particular class) that implements A. This work investigates variants of this decision problem for different implementations and a variety of Petri net classes from the point of view of classical and parameterized complexity. Also investigated is the complexity of the modification techniques of relabeling and edge, event, and state deletion, which aim to make non-implementable transition systems implementable. [Englisch]

Dokumenttyp:

Dissertation

Einrichtung:

Fakultät für Informatik und Elektrotechnik

Sprache:

Deutsch

Sachgruppe der DNB:

004 Informatik

Veröffentlichung /
Entstehung:

Rostock

Rostock: Universität Rostock

2021