Application and Theory of Petri Nets and Concurrency 1st ed. 2020. Cham : Springer International Publishing, 2020 (2020), Seite 89-108 1 Online-Ressource(XI, 437 p. 491 illus., 49 illus. in color.)
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. <dt.>
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. <engl.>
Bei der Petrinetz-Synthese soll ein gegebenes endliches beschriftetes Transitionssystem (labelled transition system; LTS) durch ein injektiv beschriftetes Petrinetz gelöst werden, was bedeutet, dass der Erreichbarkeitsgraph des Petrinetzes isomorph zum gegebenen LTS ist. Petrinetz-Synthese fing mit den Arbeiten von Ehrenfeucht und Rozenberg im Jahr 1990 an und wurde seitdem in verschiedene Richtungen erweitert. In dieser Arbeit wird die Synthese von Petrinetz-Teilklassen untersucht, beispielsweise schlichte und schlingenfreie Petrinetze. Unlösbare LTS werden durch Überapproximation behandelt. Als nächstes wird die Synthese von modalen Transitionssystemen (MTS), dem modalem μ-Kalkül und einer Teilmenge des μ-Kalküls, die konjunktiver ν-Kalkül heißt, behandelt. Das Synthese-Problem für MTS und den ν-Kalkül ist unentscheidbar, aber durch eine Einschränkung der betrachteten Petrinetze wird dieses Problem sogar für den ausdruckmächtigeren μ-Kalküls entscheidbar.
In Petri net synthesis, a given finite labelled transition system (lts) should be solved by an injectively labelled Petri net, which means that the reachability graph of the Petri net is isomorphic to the given lts. Petri net synthesis goes back to the work of Ehrenfeucht and Rozenberg in 1990, and has since then been extended in various directions.In this thesis, synthesis for subclasses of Petri nets is investigated, e.g. plain and pure nets. Unsolvable lts are handled by over-approximation. Next, synthesis from modal transition systems (mts), the modal μ-calculus, and a subset of the μ-calculus, which is called the conjunctive ν-calculus, is considered. We show that that the synthesis problem for mts and the ν-calculus is undecidable, but by restricting the Petri nets considered, the synthesis problem becomes decidable even for the more expressive μ-calculus.
SOFSEM 2017: Theory and Practice of Computer Science Cham : Springer, 2017 (2017), Seite 132-146 Online-Ressource (XVIII, 526 p. 109 illus, online resource)
This book constitutes the proceedings of the 38th International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2017, held in Zaragoza, Spain, in June 2017. Petri Nets 2017 is co-located with the Application of Concurrency to System Design Conference, ACSD 2017. The 16 papers, 9 theory papers, 4 application papers, and 3 tool papers, with 1 short abstract and 3 extended abstracts of invited talks presented together in this volume were carefully reviewed and selected from 33 submissions. The focus of the conference is on following topics: Simulation of Colored Petri Nets, Petri Net Tools.- Model Checking, Liveness and Opacity, Stochastic Petri Nets, Specific Net Classes, and Petri Nets for Pathways
Distinguished Carl Adam Petri Lecture -- Simulation of Colored Petri Nets -- Petri Net Tools -- Model Checking -- Liveness and Opacity -- Stochastic Petri Nets -- Specific Net Classes -- Petri Nets for Pathways
Lecture Notes in Computer ScienceSpringerLinkSpringer eBook Collection