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.
Letzte Änderung: 17:40 19.05.2011 Impressum