Zur Hauptnavigation Zum Inhaltsbereich Zur Suche Zum Seitenfuß


Oberseminarvorträge


Dienstag 8.7.1997 14 Uhr c.t. Raum C-221

Realisierung der verteilten Ausführung von gefärbten Petrinetzen

Heinrich Biallas

Ausgangspunkt der Überlegungen, die zum Thema dieser Diplomarbeit führten, waren Objektsysteme aus [Valk 95]. Das Werkzeug Design/CPN, in dem Petrinetze erstellt und simuliert werden können, bietet keine Möglichkeiten, Netze als Marken in Netzen (Objektsysteme) abzubilden. Daher werden Netze eines Objektsystems (Systemnetz und Objektnetze) auf mehrere Seiten eines Design/CPN-Diagrammes verteilt. Design/CPN bietet nur die Möglichkeit, Transitionen innerhalb eines Design/CPN-Diagrammes zu synchronisieren. Aus diesem Grund werden die Möglichkeiten der Interprozeßkommunikation (IPC) genutzt. Mit Hilfe der IPC können die verteilten Petrinetze miteinander kommunizieren und auf diesem Wege auch synchronisiert werden.


Dienstag 1.7.1997 14 Uhr c.t. Raum C-221

Darstellung ereignisgesteuerter Prozeßketten mit Hilfe von Petrinetzen

Jörg Rodenhagen

Im Rahmen der Gestaltung und Analyse prozeßorientierter Informationsmodelle hat sich in jüngster Zeit das ARIS-Konzept von Scheer in der Praxis weitestgehend etabliert. In diesem Konzept nimmt die Technik "Ereignisgesteuerte Prozeßkette (EPK)" die zentrale Rolle ein. Sie dient sowohl zur Spezifikation der Prozesse (und damit der dynamischen Aspekte des Gesamtmodells) als auch zur Integration weiterer sichtenspezifischer Teilmodelle.

Es hat sich herausgestellt, daß sowohl die Syntax als auch die Semantik der EPK von ihren Urhebern - meist unter Verwendung einfacher Beispiele und Kontexte - zum Teil unpräzise und unvollständig beschrieben worden ist. Durch die Aufstellung geeigneter Regeln zur Übersetzung einer EPK in Netzstrukturen sowie der Festlegung einer geeigneten Anfangsmarkierung wurden die entdeckten semantischen Lücken geschlossen. Als Gegenstand weiterführender Untersuchungen diente eine Reihe veröffentlichter EPKs der SAP AG zur Beschreibung ihres Systems R/3, die nach dem entwickelten Schema in Netze transformiert wurden.

Die Analyse der resultierenden Netze erfolgte in Form von Simulationsläufen unter Einsatz des Werkzeuges Design/CPN. Die Auswertung der Analyseergebnisse führte zur Identifikation einer Reihe konsistenter als auch inkonsistenter EPK-Strukturen, die im Vortrag vorgestellt werden.


Freitag 20. Juni 1997 13 Uhr s.t. Raum C-221

Ereignisgesteuerte Prozeßketten (EPK) und Petrinetze

Peter Langner

Nach einer Definition der Syntax für EPKs werden Regeln angegeben, um EPKs in Petri-Netze zu übersetzen. Die resultierenden Booleschen Netze sind eine Erweiterung von Stellen/Transitions-Netzen um logische Verknüpfungen und bilden eine einfache Klasse gefärbter Petri-Netze.

Das korrekte Verhalten dieser Netze läßt sich bereits durch eine algorithmische Reduktion ihrer Struktur verifizieren, eine Analyse des Fallgraphen ist nicht nötig. Eine Reihe von Modellierungsfehlern bei EPKs aus der Praxis belegt die Notwendigkeit einer solchen Netzanalyse.

EPKs mit korrektem Verhalten lassen sich zu semantisch gleichwertigen Stellen/Transitions-Netzen vereinfachen. Damit bietet die Petri-Netz-Theorie in ihrer klassischen Form ein tragfähiges Fundament zur Verifikation, Animation und Simulation von EPKs aus dem Bereich der Wirtschaftsinformatik.


Dienstag 17.06.1997 14 Uhr c.t. Raum C-221

Set-theoretic characteristics of multiprocessor system properties

Ludwik CZAJA, Warsaw University

A simple model of multiprocessor system is the following: P = (p1,p2, ...,pn), and A = (a1, a2,..., am) are collections of sequential processors and shared actions respectively. The actions may represent e.g. usage of shared resources.

Processor pi when performing its program may issue a signal rij of request for action aj. On completion of executing aj by pi, a signal of termination is issued. There is an arbiter which, on each request and termination, examines the current state of the system and issues all possible signals sij of start permission for pi to execute aj, in accordance to given synchronization rules represented by some formulae. These formulae define a behaviour of the system: they make its specification.

The signals E = { rij, tij, sij } (i = 1,...,n, j = 1,..., m) constitute an alphabet of events. Such properties like mutual exclusion, scheduling, deadlocks of various kinds, fairnesses ('strong' and 'weak'), starvations, may be formulated in terms of this simple model and translated into some set-theoretic formulae on formal languages. These languages are composed of strings (finite or not) over E. Decidability of the mentioned properties for systems generating regular and context-free languages is readily inferred from results known in the theory of formal languages.


Dienstag 10. Juni 1997 14 Uhr c.t. Raum C-221

Ausgewählte Beiträge der EUROCRYPT '97

Safuat Hamdy

Es werden einige Forschungsarbeiten vorgestellt, die auf der EUROCRYPT präsentiert wurden:


Dienstag 3. Juni 1997 14 Uhr c.t. Raum C-221

Multi-Agent-Systems based on Coloured Petri Nets

Frank Wienberg

This contribution of D. Moldt and F. Wienberg to the International Conference of Application and Theory of Petri Nets in Toulouse concerns the research area of agents.

Based on Y. Shoham's paradigm, called Agent-Oriented Programming (AOP), our approach called AOCPN (Agent-Oriented Coloured Petri Nets) regards multi-agent-systems as a specialization of distributed, Object-Oriented systems.

Agents of a multi-agent system are equipped with knowledge, general concurrent inference mechanisms dealing with this knowledge, and a declarative agent program.

These multi-agent-systems unite advantages of many contributing areas: The precise semantics of Petri nets, the abstraction and encapsulation proposed in Object-Oriented approaches, and the power of logic programming as a well-known AI-method.

As an example, an urban traffic information system will be designed which solves path searching problems in a distributed graph.


Dienstag 27. Mai 1997 14 Uhr c.t. Raum C-221

Petri's Axioms of Concurrency
A Selection of Recent Results

Olaf Kummer and Mark-Oliver Stehr

Concurrency theory, as developed by Carl Adam Petri, is an axiomatic theory of binary relations of concurrency (co) and causality (li). This talk deals with interactions between axioms and studies properties of concurrency structures, the models of this theory.

In contrast to other treatments concurrency theory will be investigated in its general form, which does not require an underlying partial order of causality.

Some difficulties are illustrated by counterexamples and possible extensions of the original set of axioms are proposed and analysed.


Dienstag, 6. Mai 1997, 14 Uhr c.t., Raum C-221

Stratified Petri Nets

Berndt Farwer

In diesem Vortrag werden aktuelle Forschungsergebisse von Eric Badouel und Philippe Darondeau vorgestellt. Der Vortrag befaßt sich mit einer Teilklasse von Valks selbstmodifizierenden Netzen, die sich als Abschluß gegenüber der Kaskade-Komposition von S/T-Netzen ergibt. Die Kaskade-Komposition von Netzen basiert auf der Idee des Kaskade-Produkts von endlichen Automaten bzw. Semi-Automaten (vgl. Ginzburg 1968).

Es werden Beziehungen zu Transitionssystemen beleuchtet und das Syntheseproblem diskutiert. Hierbei zeigt sich, daß die Zeitkomplexität dieses Problems für Stratified Petri Nets - wie auch für S/T-Netze - polynomiell ist.

Stratified Petri Nets sind dennoch flexibler als S/T-Netze und erlauben die Anwendung von Standardmethoden der linearen Algebra zu Verifikationszwecken.


Dienstag 29. April 1997, 14 Uhr c.t., Raum C-221

Heuristische Verfahren und deren Visualisierung für Numerierungsprobleme auf Graphen


Martin Stahl

Eine Vielzahl von Optimierungsproblemen läßt sich nur mit Hilfe heuristischer Verfahren mit vertretbarem Aufwand an Rechenzeit lösen. Hier wird als Beispiel dafür das Problem der (semi-)graziösen Numerierungen von Graphen herangezogen. Nach einer Darstellung des Numerierungsproblems mit Beispielen und praktischen Anwendungsmöglichkeiten wird eine allgemein einsetzbare heuristische Lösungsstrategie - der Genetische Algorithmus - vorgestellt.

Neben einer Einführung in die grundsätzliche Arbeitsweise Genetischer Algorithmen wird die Anpassung auf das Problem der (semi-)graziösen Numerierungen beschrieben. Ein Vergleich mit anderen für dieses Problem implementierten Verfahren zeigt die Leistungsfähigkeit der Genetischen Algorithmen auf.

Abschließend wird eine Demonstration des für die Erzeugung (semi-)graziöser Numerierungen entwickelten Programms gegeben. Die Software ermöglicht auch die Visualisierung der Numerierungen sowie der Verfahren zur Erzeugung der Numerierungen; dies wird beispielhaft gezeigt.


Dienstag 15. April 1997, 14 Uhr c.t., Raum C-221

Lineare Gleichungs- und Ungleichungssysteme, ihre Lösungen und deren Komplexität


Jens Bockentin

Lineare Gleichungs- und Ungleichungssysteme sind bereits seit langer Zeit ein Untersuchungsgegenstand von Mathematikern und Informatikern. Neben der Frage nach der Lösbarkeit eines linearen Systems interessiert einen Informatiker vor allem, mit welchem Algorithmus eine Lösung für so ein System gefunden werden kann und wie schwer bezüglich Zeit- bzw. Speicherplatzaufwandes ein solcher Algorithmus ist. Je nach Problemstellung variiert diese Komplexität erheblich.

Für die Problemstellung gibt es zahlreiche Möglichkeiten. Neben der Art des Vergleichsoperators ist von Bedeutung, ob die zu suchende Lösung in einer bestimmten Menge, beispielsweise der Menge der ganzzahligen Zahlen, liegen muß. Ein wichtiger Spezialfall liegt vor, wenn die rechten Seiten der Gleichungen bzw. Ungleichungen den Nullvektor bilden.

Viele der Problemstellungen sind bereits behandelt worden, es herrscht jedoch eine gewisse Unübersichtlichkeit über die Ergebnisse, die auch schon in falsche Ergebnisse mündete. Die im Seminar vorzustellende Diplomarbeit faßt die Ergebnisse zusammen und schließt einige Lücken.


Dienstag, 8. April 1997 um 14 Uhr c.t.- Raum C-221

Eine auf Petri-Netzen basierende Koordinationssprache


Claus Aßmann
Christian-Albrechts-Universität zu Kiel

Koordinationssprachen stellen eine mögliche Lösung für die vielfältigen Schwierigkeiten beim Programmieren verteilter Systeme dar. Sie trennen die algorithmische Spezifikation von der Spezifikation der Kommunikationen. Koordinationssprachen, die auf höheren Petri-Netzen basieren, haben eine Reihe von Vorteilen gegenüber anderen Lösungen: Sie bieten eine leicht verständliche graphische Darstellung, eine intuitive Semantik und eine formale Basis, die die Verifikation von wichtigen Systeminvarianten erlaubt. Außerdem ist die Trennung zwischen beiden Spezifikationsebenen vollständig, während in vielen anderen Ansätzen Koordinations- und Programmiersprache im Sourcecode miteinander verwoben sind.

Aufbauend auf einer Variante von gefärbten Petri-Netzen wurde eine Koordinationssprache K2 entwickelt. Diese verwendet eine eingeschränkte Netzklasse (Synchronisationsgraphen), wobei sogenannte atomare Prozesse Programme als Inschriften haben, die die Berechnungen auf den zugeführten Daten vornehmen. Zusätzlich stehen einige wenige primitive Prozesse (Switch, Select, Merge) zur Verfügung, hierarchische Prozesse zur Abstraktion von Teilnetzen, rekursive Prozesse zur dynamischen Anpassung von Netzen an unterschiedliche Eingaben und zustandsbasierte Prozesse für Filter- und Erzeugerprozesse.

Der im Betastadium befindliche K2-Compiler benutzt PVM als Basis für die Laufzeitumgebung, wodurch der erzeugte Code auf verteilten Systemen ausgeführt werden kann.

Letzte Änderung: 17:40 19.05.2011
Impressum