title: |
Zur Komplexität der Synthese von Petri-Netzen |
|
contributing persons: |
Ronny Tredup[VerfasserIn] |
|
1246043041 |
Karsten Wolf[AkademischeR BetreuerIn] |
|
124773052 |
|
Universität Rostock |
Robert Lorenz[AkademischeR BetreuerIn] |
|
Universität Augsburg |
|
contributing corporate bodies: |
Universität Rostock[Grad-verleihende Institution] |
|
38329-6 |
Universität Rostock, Fakultät für Informatik und Elektrotechnik[Grad-verleihende Institution] |
|
10085032-7 |
|
|
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.
[German] |
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.
[English] |
|
document type: |
|
institution: |
Faculty of Computer Science and Electrical Engineering |
|
language: |
|
subject class (DDC): |
004 Data processing Computer sciences |
|
|
publication / production: |
Rostock
Rostock: Universität Rostock
|
2021
|
|
statement of responsibility: |
vorgelegt von Ronny Tredup |
|
|
identifiers: |
|
|
access condition: |
|
license/rights statement: |
all rights reserved This work may only be used under the terms of the German Copyright Law (Urheberrechtsgesetz). |
|
|
RosDok id: |
rosdok_disshab_0000002635 |
created / modified: |
18.11.2021 / 08.08.2023
|
metadata license: |
The metadata of this document was dedicated to the public domain (CC0 1.0 Universal Public Domain Dedication). |