Characterisation of a Class of Petri Net Solvable Transition Systems

20. April 2018

Organisator:  Evgeny Erofeev, M. Sc.

Ort:  OFFIS-Gebäude, Raum D21

M i t t e i l u n g 

Im Rahmen der Disputation seines Promotionsverfahrens hält Herr Evgeny Erofeev, M.Sc., seinen öffentlichen Vortrag zum Thema

„Characterisation of a Class of Petri Net Solvable Transition Systems”

am Freitag, den 20. April 2018, um 14.30 Uhr im OFFIS-Gebäude, Raum D21.

Abstract:

The problem of Petri net synthesis is widely studied in the literature, being set in a range of contexts. At the same time, the question for a characterisation of synthesisable state spaces, which is related to synthesis, 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. We study a relatively restricted class of transition systems representing the reachability graph of the sought Petri net. Looking at the case with only two transitions allows to obtain notable results, not only at characterising of state spaces but also at synthesising of the Petri net.

Among such results is a language-theoretical characterisation of finite binary sequences and cycles synthesisable into a Petri net. Synthesis algorithms, based on the characterisation, demonstrate a better runtime in comparison to the region based synthesis.

A classification for a complete enumeration of minimal unsolvable binary words is presented. This classification gives rise to a characterisation for the class of all minimal unsolvable words in the form of extended regular expressions. A procedure for pre-synthesis, which recognises failures early and uses the characterisation, demonstrates good results for rejecting a given input, without having to start the synthesis process itself.

For Petri nets over the binary transition set, a graph-theoretical characterisation of their reachability graphs is presented in the form of state spaces which are geometrically convex sets. The characterisation relies on the notion of generalised cycles. Based on this characterisation and the absence of Parikh-non-zero g-cycles, an algorithm for an over-approximating a finite language
by a Petri net language is suggested.

Mit der Teilnahme von Zuhörerinnen und Zuhörern an der anschließenden
Prüfung bis 16.00 Uhr ist Herr Erofeev nicht einverstanden.

gez. Prof. Dr.-Ing. A. Hahn