Erofeev, Evgeny (2018) Characterisation of a class of Petri net solvable transition systems. PhD, Universität Oldenburg.

Preview

Volltext (1289Kb)

Abstract

The problem of Petri net synthesis is widely studied in the literature, set in a range of contexts, while the question for characterisation of synthesisable state spaces seems to be less investigated and developed. The current work is an attempt to put more insight into the latter, keeping in mind the former as the main goal. Among the main results of the work, a graph-theoretical characterisation of synthesisable linear transition systems and cycles is presented. Synthesis algorithms, based on the characterisation, demonstrate a better runtime in comparison to the region based synthesis. For the class of minimal unsolvable binary sequences, a characterisation is suggested in the form of extended regular expressions. The state spaces of Petri nets over the binary transition set are proven to be geometrically convex hulls. An algorithm for over-approximating a finite language by a Petri net language is presented.

["eprint_fieldname_title_plus" not defined]

Charakterisierung von der Klasse der in Petrinetz synthetisierbaren Transitionssystemen

["eprint_fieldname_abstract_plus" not defined]

Das Problem der Petrinetzsynthese wurde schon weit untersucht und passt in viele Kontexte. Gleichzeitig scheint die Frage nach einer Charakterisierung von synthetisierbaren Zustandsräumen weniger entwickelt zu sein. Die vorliegende Arbeit ist ein Versuch ein besseres Verständnis von letzterem zu erlangen, während ersteres als Hauptziel im Auge behalten wird. Zu den Hauptresultaten der Arbeit gehört eine Graph-theoretische Charakterisierung von synthetisierbaren linearen Transitionssystemen und Kreisen. Auf dieser Charakterisierung basierende Synthesealgorithmen zeigen eine bessere Laufzeit im Vergleich zur Regionen-basierten Synthese. Eine Charakterisierung der Klasse aller minimal-unlösbaren Wörter wird in Form eines erweiterten regulären Ausdrucks vorgeschlagen. Die Zustandsräume von Petrinetzen Über der binären Transitionsmenge erwiesen sich als geometrisch konvexe Hüllen. Ein Algorithmus zur Überapproximation einer endlichen Sprache durch eine Petrinetzsprache wird dargestellt.

Item Type:	Thesis (PhD)
Uncontrolled Keywords:	Petri-Netz, Synthese, Transitionssystem, Binärwort
Divisions:	School of Computing Science, Business Administration, Economics and Law > Department of Computing Science
Date Deposited:	22 Feb 2019 10:34
Last Modified:	25 Feb 2019 09:26
URI:	https://oops.uni-oldenburg.de/id/eprint/3942
URN:	urn:nbn:de:gbv:715-oops-40238
DOI:
Nutzungslizenz:

Actions (login required)

View Item