Oberseminarvorträge
Dienstag, 13. Juli 1999, 14 Uhr c.t., Raum C-221
Algebraische Petrinetze
Bodo Möller
Die ursprüngliche Definition der Petrinetze stellt keine Endlichkeitsforderungen an die Mengen der Stellen und Transitionen und an die Menge der Marken in einer Markierung. Solche Einschränkungen (Markierungen als Elemente eines freien kommutativen Monoids) werden jedoch oft hinzugefügt und sind u.a. beim üblichen Begriff der S-Invarianten vorausgesetzt.
Bei der algebraischen Spezifikation gefärbter Petrinetze können Endlichkeitsfragen mitbehandelt werden, indem Gleichungsspezifikationen zu Endlichkeitsspezifikationen erweitert werden: Diese erlauben die algebraische Bestimmung von S-Invarianten, die auch für Netze mit unendlichen Markierungen und mit unendlich nebenläufigen Schaltvorgängen eine Bedeutung haben.
Dienstag, 22. Juni 1999, 14 Uhr c.t., Raum C-221
Gedanken zur Linear-Logischen Darstellung von strukturellen Petrinetz-Modifikationen
Berndt Farwer
Die Modifikation von Petrinetzstrukturen hat sich als eine wünschenswerte Erweiterung des Grundkonzeptes der Netze herausgestellt. Es werden zunächst Probleme bei der Modellierung durch lineare Logik aufgezeigt, die bei der Verwendung von Standard-Fragmenten und deren Kalküle auftreten. Anhand der bisher untersuchten Korrespondenzen zwischen Petrinetzen und Linearer Logik wird versucht, eine Grundlage für einen modifizierten Kalkül zu entwickeln, der als Basis für die Darstellung struktureller Modifikationen an S/T-Netzen dienen kann.
Dienstag, 15. Juni 1999, 14 Uhr c.t., Raum C-221
Symmetric communication between coloured Petri net simulations and Java-processes
O. Kummer, D. Moldt, and F. Wienberg
In order to widen the applicability of Coloured Petri nets for the specification and design of large scale distributed applications, a framework has been developed that supports the interaction of Design/CPN and Java processes. The underlying architecture can be used for other tools. Thereby a seamless embedding of the two worlds of Petri nets and object-oriented programming is achieved, allowing problem oriented modeling at different abstraction levels in a fully distributed environment.
The general possibilities to connect Coloured Petri net simulations with remote processes are discussed and a specific implementation of the required framework is sketched. Promising application areas are named and for some of them concrete example models are provided.
Dienstag, 8. Juni 1999, 14 Uhr c.t., Raum C-221
Zur Formalisierung von Objekt-Netz-Prozessen
Rüdiger Valk
Wert- und Referenz-Semantik unterscheiden sich in Objekt-Petrinetzen bei Verteilung der Objektstruktur auf unterschiedliche Orte. Während bei der Referenz-Semantik Referenzen auf das nach wie vor als Unikat weiterbestehende Objekt zeigen, werden in der Wert-Semantik Kopien verteilt, die dann ein voneinander unabhängiges, dynamisches Verhalten haben. Beide Fälle sind relevante Erscheinungen in verteilten Informatiksystemen. In dem Vortrag werden die Semantiken verglichen, und es werden formale Kriterien für ihr Übereinstimmen vorgestellt. Die am 4.5.1999 eingeführten Prozesskonzepte werden durch neue Techniken formalisiert.
Dienstag, 25. Mai 1999, 14 Uhr c.t., Raum C-221
Konzeption, Evaluierung und Implementation eines Akzelerators für elliptische Kurven unter Berücksichtigung praktischer Randbedingungen bei kryptographischen Anwendungen
Siegmund Gorr
Vorstellung des Berechnungskonzepts für die Gruppenoperation elliptischer Kurven über dem Erweiterungskörper GF(2k), mit k zwischen 160 und 200. Skizzierung des Anwendungsbereichs im Gebiet Low-Security. Eingliederung des Chip in ein Anwendungssystem. Vergleich zu RSA und anderen modular-exponentiellen Krypto-Verfahren. Beschreibung der aufgetretenen Probleme unter Berücksichtigung der Layoutgröße, Laufzeit und Leistungsaufnahme. Diskussion über Berechnungsalternativen.
Dienstag, 18. Mai 1999, 14 Uhr c.t., Raum C-221
Neue Iterationslemmata für Reguläre, Lineare, Kontextfreie und Linear Indizierte Sprachen
Manfred Kudlek
Nach einer Übersicht über bisherige Iterationslemmata werden neue stärkere Iterationslemmata für kontextfreie Sprachen vorgestellt, welches sowohl die untere Schranke der ausgezeichneten Positionen eines Wortes als auch die obere Schranke der ausgezeichneten Positionen des mittleren Teiles im Bader-Moura-Lemma verschärfen. Ferner werden auch neue Iterationslemmata für reguläre und lineare Sprachen präsentiert, als auch für linear indizierte Sprachen.
Dienstag, 11. Mai 1999, 14 Uhr c.t., Raum C-221
Faktorisierung von Polynomen
Edward Kulic
Vorgestellt werden die beiden Themengebiete Polynomfaktorisierung und Gröbnerbasen, die auf den ersten Blick nicht viel gemeinsam haben.
Die Polynomfaktorisierung spielt dort überall eine Rolle, wo man die Zerlegung eines bzw. mehrerer Polynome in seine Faktoren benötigt. Aus der Vielzahl der bekannten Faktorisierungsverfahren soll das Verfahren von Becker und Weispfenning vorgestellt werden. Bei Problemen, die auf dem ggT einer Polynommenge basieren, sind diese Polynomfaktorisierungsverfahren im Nachteil, da sie auf jedes Polynom einzeln angewendet werden müssen und erst durch Vergleich der Faktoren der ggT bestimmt werden kann. Hier sind die Gröbnerbasen von Vorteil, da deren Berechnung, ausgehend von der Polynommenge, sofort den ggT liefern. Es soll deshalb neben einer Einführung auch darauf eingegangen werden, wie die Gröbnerbasen mit dem ggT und dem Euklidischen Algorithmus zusammenhängen. Insbesondere wird sich dabei zeigen, daß die Gröbnerbasen und deren Berechnung eine Verallgemeinerung des ggT's und des Euklidischen Algorithmus darstellen. Da zudem die Gröbnerbasen die Grundlage für die Lösung einer Vielzahl von Problemen mit Polynommengen bilden, soll auch auf deren Anwendungsbereiche eingegangen werden.
Dienstag, 4. Mai 1999, 14 Uhr c.t., Raum C-221
Wert- und Referenz-Semantik von Objekt-Petrinetzen im Vergleich
Rüdiger Valk
Wert- und Referenz-Semantik unterscheiden sich in Objekt-Petrinetzen bei Verteilung der Objektstruktur auf unterschiedliche Orte. Während bei der Referenz-Semantik Referenzen auf das nach wie vor als Unikat weiterbestehende Objekt zeigen, werden in der Wert-Semantik Kopien verteilt, die dann ein voneinander unabhängiges, dynamisches Verhalten haben. Beide Fälle sind relevante Erscheinungen in verteilten Informatiksystemen. In dem Vortrag werden die Semantiken verglichen, und es werden formale Kriterien für ihr Übereinstimmen vorgestellt.
Dienstag, 27. April 1999, 14 Uhr c.t., Raum C-221
Die Lösung der Vermutung von Hartmanis für dünne Mengen in NSPACE(log n)
Bernd Kirsig
Für die strukturelle Komplexitätstheorie ist es von großem Interesse, Antworten auf die Fragen zu finden, ob P = NP und L = NL ist. Eine wichtige Rolle bei der Untersuchung dieser Fragen spielen vollständige Mengen für diese Komplexitätsklassen.
In diesem Zusammenhang formulierten Berman und Hartmanis 1977 und 1978 drei Vermutungen:
- Vermutung: Alle NP-vollständigen Sprachen sind paarweise zueinander isomorph.
- Vermutung: Falls P ungleich NP, so kann keine NP-vollständige Sprache dünn sein.
- Vermutung: Falls L ungleich NL, so kann keine NL-vollständige Sprache dünn sein.
Die erste Vermutung ist natürlich noch ungelöst, da der Nachweis dieser Vermutung gleichzeitig P ungleich NP liefert. Die zweite Vermutung wurde 1982 von Mahaney bestätigt. Die dritte Vermutung erwies sich allerdings als ein schwierigeres Problem, das erst 1995 von Cai und Sivakumar gelöst werden konnte.
Der Beweis von Cai und Sivakumar soll in diesem Vortrag vorgestellt werden, da er einige interessante neue Techniken benutzt.
Dienstag, 20. April 1999, 14 Uhr c.t., Raum C-221
Algebraische Strukturen von Objektnetzen
Michael Köhler
In letzter Zeit ist neben der Anforderung, große Anwendungen zu entwickeln, auch die Forderung nach Verteiltheit ins Blickfeld der Informatik gerückt. Zur Beschreibung von Verteiltheit und nebenläufigem Verhalten in Rechensystemen aller Art haben sich Petri-Netze bewährt. Da für die Entwicklung großer, verteilter Anwendungen kein etabliertes Programmiermodell existiert, untersuchen neuere Arbeiten auf dem Gebiet der Netz-Theorie, ob Petri-Netze um objektorientierte Eigenschaften erweitert werden können, um nicht nur als Beschreibungs-, sondern auch unmittelbar als Entwicklungssprache für verteilte Anwendungen dienen zu können. Dieser Vortrag geht zunächst auf die Unterschiede zwischen Referenz- und Wertsemantik ein, die in verschiedenen Ansätzen Verwendung finden, um dann einen Ansatz zu präsentieren, der einen vertieften Einblick in die Struktur der Objektsysteme nach Valk eröffnen soll.
Dienstag, 13. April 1999, 14 Uhr c.t., Raum C-221
Untersuchung der Einsatzmöglichkeiten von Petrinetz-Konzepten in der objektorientierten Analyse am Fallbeispiel eines Reiseunternehmens
Marc Netzebandt
Petrinetze eignen sich sehr gut zur Modellierung von dynamischem Systemverhalten und zur Darstellung von Nebenläufigkeit. Sie bestehen aus wenigen grafischen Elementen und können wegen ihrer Ausführbarkeit gut zum Prototyping eingesetzt werden. Deshalb werden Petrinetze oftmals zur Spezifikation von Systemen verwendet. Weit verbreitet sind zur Zeit inkrementelle Softwareentwicklungsprozesse. Besteht die Spezifikation aus nur einem Petrinetzmodell, so wird dieses mit zunehmender Größe unflexibel bezüglich Änderungen. Eine Lösung dieses Problems bietet die Übertragung von objektorientierten Konzepten auf Petrinetze. Das Resultat sind objektorientierte gefärbte Petrinetze (object-oriented coloured petri nets - OOCPN) mit den Vorteilen der Objektorientierung und denen der Petrinetze.
Vorgestellt werden Konzepte für objektorientierte Petrinetze und deren Einsatz im Bereich der objektorientierten Systemanalyse zur Entwicklung einer ausführbaren Systemspezifikation. Ein einfaches Reiseunternehmen dient als Fallbeispiel. In Kombination mit einigen Techniken der Unified Modeling Language (UML) werden evolutionäre Petrinetz-Prototypen erstellt. Jeder Petrinetz-Prototyp ist ausführbar und ermöglicht die Simulation bestimmter Abläufe im System. Durch diese Veranschaulichung des modellierten Systemverhaltens lassen sich Fehlentwicklungen rechtzeitig erkennen. Die Datenkapselung durch die Objektorientierung vereinfacht die nachträgliche Integration von geänderten Anforderungen. Die Möglichkeiten und Beschränkungen des erfolgreich umgesetzten Ansatzes werden am prinzipiellen Aufbau der OOCPN-Modelle diskutiert und anhand von Ausschnitten des 90 Seiten umfassenden PN-Modells demonstriert.
