Sie befinden sich hier: KU.de  Fakultäten  Mathematisch-Geographische Fakultät  Informatik  Projekte  Synops  

Synops- Synthese von Petrinetzen aus Szenarien (2007 - 2009)

Zusammenfassung

Leiter

Ansprechpartner

Ziele

Publikationen

Eingeladene Vorträge

Diplomarbeiten

Workshops

Verwandte Projekte

Zusammenfassung

Das Verhalten eines Petrinetzes kann gegeben sein durch die Menge seiner Schalt- oder Schrittfolgen, durch Erreichbarkeitsgraphen, aber auch durch halbgeordenete Ereignismengen, die oft als beschriftete azyklische Graphen dargestellt werden. Die zuletzt genannte Semantik erlaubt die explizite Darstellung von kausaler Unabhängigkeit; zwei Ereignisse finden unabhängig statt, wenn sie im Graphen nicht geordnet sind. Während derartige halbgeordnete Semantiken in der Theorie seit langer Zeit betrachtetet werden, finden sie erst in jüngerer Zeit in Anwendungen Beachtung, insbesondere in den Bereichen Geschäftsprozessmodellierung, Webdienste und Eingebettete Systeme, meist in Form verschiedener Varianten von Sequenzdiagrammen.

Die traditionelle Vorgehensweise beim modellbasierten Systementwurf - Konstruktion eines Modells und anschließende explizite oder implizite Betrachtung seines Verhaltens - wird vielfach abgelöst durch eine umgekehrte Vorgehensweise: Das Verhalten wird zunächst formalisiert und modelliert, und das Systemmodell wird daraus anschließend automatisch synthetisiert. Während für Petrinetze entsprechende Syntheseverfahren für Schrittfolgen und Erreichbarkeitsgraphen bekannt sind und in der Praxis eingesetzt werden, fehlen Verfahren für die Synthese von Petrinetzen aus halbgeordneten Verhaltensbeschreibungen. Die Entwicklung derartiger Verfahren, ihre Implementierung und Erprobung ist Gegenstand dieses Vorhabens.

Ausgangspunkt sind jüngere Ergebnisse des Antragstellers, die den für Erreichbarkeitsgraphen bekannten Begriff einer ''Region'' auf halbgeordnete Abläufe verallgemeinert. Damit ist die Synthese von Petrinetzen aus halbgeordneten Abläufen grundsätzlich Regionen-basiert möglich. Das bislang entwickelte theoretische Konzept wird verfeinert und implementiert. Es wird verallgemeinert auf höhere Netzklassen und auf Petrinetze mit Erweiterungen um Zeit, Kosten usw., wie sie in der Praxis eingesetzt werden.

Das Projekt knüpft an die früheren DFG-Projekte VIP und SPECIMEN von Prof. Dr. J. Desel an, in denen Petrinetze in der Geschäftsprozessmodellierung bzw. der Steuerungssynthese eingesetzt wurden. An der Durchführung des Projekts SPECIMEN war der Antragsteller mitverantwortlich als lokaler Koordinator beteiligt. Aus dem Projekt VIP entstand das Werkzeug VIPtool, für dessen Pflege und Weiterentwicklung der Antragsteller verantwortlich ist und auf das die Implementierung der Syntheseverfahren aufbaut. Der direkte Bezug zu diesen Anwendungsfeldern stellt die anwendungsorientierte Ausrichtung des Vorhabens sicher.



nach oben

Leiter

PD. Dr. habil. Robert Lorenz
Tel.: 08421/93-1137 
email: robert.lorenz@ku-eichstaett.de 
Mathematisch-Geographische Fakultät 
Institut für Informatik
Kath. Universität Eichstätt


nach oben

Ansprechpartner

Dipl. Math. oec.Kölbl Christian
Tel.: 08421/93-1161 
email: christian.koelbl@ku-eichstaett.de 
Mathematisch-Geographische Fakultät 
Institut für Informatik
Kath. Universität Eichstätt


nach oben

Ziele

Das Gesamtziel dieses Vorhabens ist die Entwicklung effizienter Methoden zur Synthese von Petrinetzen aus Verhaltensbeschreibung bzgl. der Halbordnungssemantik, deren Implementierung und deren exemplarische Anwendung in den Bereichen Geschäftsprozessmodellierung, Webdienste, eingebettete Systeme und Steuerungssysteme. Zur Erreichung dieses Ziels definieren wir die folgenden Teilziele. Die Arbeitspakete, die diesen Teilzielen zugeordnet sind, werden nicht nacheinander, sondern teilweise überlappend durchgeführt, so dass die Erreichung dieser Teilziele sich in verschiedenen Aspekten gegenseitig bedingt.

S/T-Netze
Das Syntheseproblem für S/T-Netze aus halbordnungsbasierten Verhaltensbeschreibungen soll, ausgehend von den Ergebnissen der Vorarbeiten des Antragstellers (und der Arbeitsgruppe des Lehrstuhls), vollständig gelöst werden. Dazu sollen sowohl Sprachen-basierte (z.B. basierend auf Termen) als auch Graphen-basierte Darstellungen der Halbordnungssemantik (und einzelner Abläufe) berücksichtigt werden. Insbesondere muss die Schwierigkeit gelöst werden, auch unendliche Abläufe und unendliche Mengen von Abläufen endlich darzustellen. Für die Repräsentation der Menge aller Abläufe gibt es im traditionellen, sequentiellen Fall ebenfalls Graphen-basierte Darstellungen wie z.B. den Erreichbarkeitsgraphen. Dieser definiert zusätzlich eine Äquivalenz auf einzelnen Abläufen (derselbe globale Zustand wird erreicht). Eine entsprechende Notation für Mengen halbgeordneter Ablaufbeschreibungen soll entwickelt werden. Hierbei gehen wir von den bekannten Konzepten der Ereignis-Strukturen und der endlichen Präfixe von Entfaltungen aus, die aber stets mit azyklischen Graphen beschrieben werden, so dass unendliches Verhalten entweder nur indirekt oder durch unendliche Strukturen beschreibbar ist.

Implementierung
Die entwickelten Syntheseverfahren für S/T-Netze werden implementiert. Dafür verwenden wir das am Lehrstuhl der Arbeitsgruppe existierende Werkzeug VIPtool, integrieren also die entwickelten Syntheseverfahren in die Funktionalität des VIPtools. Die Algorithmen werden mit Hilfe von aus der Literatur bekannten Fallstudien sowie mit Fallstudien aus den im Projekt betrachteten Anwendungsbereichen evaluiert.

Anwendung
Es werden Vorgehensmodelle für den Werkzeug-unterstützten Modellentwurf entwickelt, die an den in den Projekten SPECIMEN und VIP entwickelten Vorgehensmodellen anknüpfen, aber wesentlich auf der Modellsynthese aus halbordnungsbasierten Verhaltensbeschreibungen basieren. Die aus diesen Projekten und aus weiteren Industrieprojekten vorliegenden Beispiele werden exemplarisch mit Hilfe dieses Vorgehensmodells fiktiv nochmals entwickelt. Die dabei auftretenden Schwierigkeiten und Lücken werden dokumentiert, finden aber auch Berücksichtigung bei der Verfeinerung der anderen Teilziele.

Erweiterungen um Daten, Zeit, Kosten
(Die Erreichung dieses Teilziels ist Schwerpunkt des Projektes im dritten Projektjahr, das in diesem Projektantrag bereits mitkonzipiert ist, auch wenn zunächst nur die Bewilligung für 24 Monate beantragt werden kann)
S/T-Netze abstrahieren in verschiedener Weise zu stark von Aspekten, die in realen Anwendungen von hoher Relevanz sind. Dazu gehören die Berücksichtigung von Daten, Zeit, Kosten, Einschränkungen der Nebenläufigkeit durch knappe Ressourcen und durch Schreibzugriffe, asymmetrische Synchronisation von Ereignissen (wie sie durch sog. ''Event Arcs'' ausgedrückt wird) usw. Diese Aspekte können in Petrinetzen durch verschiedenartige syntaktische Ergänzungen berücksichtigt werden. Der semantische Bereich dieser syntaktischen Ergänzungen liegt vielfach außerhalb des Bereichs der halbgeordneten Abläufe (z.B.\ Kostenaspekte), hat aber teilweise durchaus Einfluss auf die Abhängigkeitsstrukturen der Ereignisse in Abläufen (z.B.\ Ressourcenzugriffe). Um die im vorigen Teilziel formulierten Anwendungsbeispiele möglichst realitätsnah durchführen zu können, müssen die für die Synthese relevanten Aspekte identifiziert werden und die Syntheseverfahren entsprechend erweitert werden. Diese Erweiterungen, aber teilweise auch Erweiterungen, die keinen unmittelbaren Einfluss auf die Syntheseverfahren haben, werden im Vorgehensmodell, in der Implementierung und in den Anwendungsbeispielen mitberücksichtigt.



nach oben

Publikationen


2009

2008
  • R. Bergenthum, R. Lorenz, S. Mauser: Faster Unfolding of General Petri Nets based on Token Flows. Submitted to 29th international conference on Application and Theory of Petri Nets (ICATPN), 2008.
  • R. Lorenz, S. Mauser: Variants of the Language Based Synthesis Problem for Petri Nets. Submitted to 29th international conference on Application and Theory of Petri Nets (ICATPN), 2008.
  • R. Bergenthum, J. Desel, R. Lorenz, S. Mauser: Synthesis of Petri Nets with Viptool. Submitted to 29th international conference on Application and Theory of Petri Nets (ICATPN), 2008.
  • R. Bergenthum, J. Desel, R. Lorenz, S. Mauser: Synthesis of Petri Nets from Infinite Partial Languages. Submitted to 8th international conference on Application of Concurrency to system Design (ACSD), 2008.
  • R. Bergenthum, J. Desel, G. Juhás, R. Lorenz, S. Mauser: Executability of Scenarios in Petri Nets. Submitted to Theoretical Computer Science.
  • G. Juhás, R. Lorenz, S. Mauser: Complete Process Semantics of Petri Nets. Submitted to Fundamenta Informaticae.
  • R. Lorenz, R. Bergenthum, J. Desel, S. Mauser: Synthesis of Petri nets from finite partial languages. Accepted for Fundamenta Informaticae (2009).
  • G. Juhás, R. Lorenz, S. Mauser: Causal Semantics of Algebraic Petri Nets distinguishing Concurrency and Synchronicity. Accepted for Fundamenta Informaticae (2008).
  • J. Desel: From Human Knowledge to Process Models. Proceedings of UNISCON (to appear) , 2008.
  • J. Desel, R. Bergenthum, S. Mauser: Synthesis of Petri Nets for Business Process Design. Submitted to Verhaltensmodellierung: Best Practices und neue Erkenntnisse, Workshop an der Modellierung, 2008.

2007

nach oben

Eingeladene Vorträge

  • R. Lorenz: Synthese von Petrinetzen aus Sprachen: Methodik und Anwendung im Bereich des Workflow Mining . Invited Talk at: Institute for Systems Engineering, Section Simulation (Prof. Helena Szczerbicka), University Hannover, Germany, 2007
  • R. Lorenz: How to synthesize Petri nets from languages: a survey. Invited Talk at: Department of Mathematics and Computer Science (Prof. W.M.P. van der Aalst), Technical University of Eindhoven (TU/e), Netherlands, 2007.
  • R. Lorenz: How to Synthesize Petri Nets from Languages: a survey. Invited Talk at: Department of Computing and Software (Prof. Ryszard Janicki), McMaster University Hamilton/Ontario, Kanada, 2007
  • R. Lorenz: Synthesis of Petri nets from Languages: Methods and Application in the Area of Workflow Mining. Invited Talk at: School of Computer Science (Ass. Prof. Joanne M. Atlee), University of Waterloo/Ontario, Kanada, 2007
  • R. Lorenz: How to Synthesize Petri Nets from Languages: a survey. Invited Talk at: Department of Electrical & Computer Engineering (Ass. Prof. Sandeep Shukla), Virginia Tech, USA, 2007

Diplomarbeiten

  • B. Weixelbaum: Synthese von Petrinetzen aus partiellen Sprachen mit Methoden der linearen Programmierung, aktuell
  • K. Mohr: Effizientes Process-Mining mit Hilfe Regionen-basierter Synthese-Methoden, aktuell

Workshops

  • 2008 Satellite workshop of the International Conference on Application and Theory of Petri Nets. Process Mining and Petri Net Synthesis.

Verwandte Projekte

  • Softwareprojekt VipTool zur halbordnungsbasierten Simulation, Validierung, Verifikation und Synthese von Petrinetz-Modellen
    Lehrstuhl füur Angewandte Informatik an der KUE (mit Studenten)
    Implementierung und Evaluierung von Synthese-Algorithmen
  • DAAD-Projekt über Scenario-based Approaches for Misbehavior Detection in Ad Hoc Wireless Networks
    Lehrstuhl für Angewandte Informatik an der KUE
    FG Simulation und Modellierung der Universität Hannover
    Department of Applied Informatics of the Slovak University of Technology
    Anwendung von Petrinetz-Synthese- und Verifikationsverfahren zur Entdeckung von Fehlverhalten in Ad Hoc Wireless Netzwerken

letzte Änderung am  Robert Lorenz