Oberseminarvorträge

Dienstag, 20. Januar 1997, 14 Uhr c.t., Raum C-221

Termersetzung und Nebenläufigkeit

Mark-Oliver Stehr

Wir betrachten Termersetzungssysteme als Modell zur Beschreibung nebenläufiger Systeme: Ein Term beschreibt einen (Teil-)-Zustand des Systems und die Ersetzungsregeln legen die möglichen Zustandsübergänge fest. Zur Modellierung der Nebenläufigkeit wird die natürliche Parallelität von Termersetzungsysteme genutzt. Der Grad der Nebenläufigkeit und die Art der Verteiltheit läßt sich durch Ersetzen modulo einer geeigneten Äquivalenzrelation erhöhen bzw. der Anwendung anpassen.

Als konkretes Modell wird im Vortrag die von Meseguer 1992 vorgeschlagene Rewriting Logic vorgestellt, die algebraische Spezifikationen und die Beschreibung nebenläufiger Systeme vereinheitlicht. Die Idee zur Rewritung Logic stammt aus einer kategorientheoretischen Verallgemeinerung von S/T-Netzen Ende der 80er Jahre (Slogan: "Petri Nets are Monoids").

Im Vortrag sollen exemplarisch anhand eines verteilten Netzwerkalgorithmus mögliche Übersetzungen zwischen Rewriting Logic und nicht nur S/T-Netzen sondern auch algebraischen Petrinetzen erörtert werden. (Teil-)Implementierungen der Rewriting Logik wie die Sprache "Maude" können mit Hilfe solcher Übersetzungen zur Ausführung von algebraischen Petrinetzen eingesetzt werden. Ferner lassen sich mit einer geeigneten Übersetzung Techniken z.B. aus dem Bereich der Semantik, Verifikation, der Objektorientierung oder der Agentenorientierung zwischen beiden Formalismen austauschen.

Dienstag, 13. Januar 1997, 14 Uhr c.t., Raum C-221

Vollst�ndige d�nne Mengen

Bernd Kirsig

Eine Sprache L über dem Alphabet {0,1} kann f�r jede L�nge n 2ⁿ Worte dieser L�nge enthalten. Eine Menge S wird als d�nn bezeichnet, wenn es ein Polynom p gibt, so da� S f�r jedes n von diesen 2ⁿ Kandidaten h�chstens p(n) Worte enth�lt.

D�nne Mengen sind wahrscheinlich nicht in der Lage, die Komplexit�t ganzer Komplexit�tsklassen einzufangen. So h�tte z.B. die Existenz einer d�nnen NP-vollst�ndigen Menge P = NP zur Folge.

Da das Studium von Komplexit�tsklassen und Sprachfamilien durch die Untersuchung ihrer vollst�ndigen Mengen (sofern welche existieren) erheblich erleichtert wird, stellt sich nun die Frage, ob d�nne Mengen �berhaupt vollst�ndige Sprachen enthalten k�nnen.

Eine besondere Schwierigkeit besteht in der Tatsache, da� zun�chst einmal �berhaupt keine Charakterisierung der d�nnen Mengen in NSPACE(log n) durch ein spezielles Maschinenmodell o.�. vorhanden ist. Solche Charakterisierungen sind im allgemeinen erforderlich, um n�here Aussagen �ber eine Sprachklasse zu treffen.

In dem Vortrag wird gezeigt, wie Turingmaschinen so modifiziert werden k�nnen, da� sie nur noch d�nne Mengen erkennen k�nnen. Am Beispiel der Klasse NSPACE(log n) wird dann (unter Verwendung dieser speziellen Maschinen) gezeigt, da� die d�nnen Mengen in NSPACE(log n) vollst�ndige Sprachen besitzen.

Dienstag, 16. Dezember 1997, 14 Uhr c.t., Raum C-221

Agentenorientierung und höhere Petrinetze zur Spezifikation verteilter, offener Systeme mit dynamischer Struktur

Daniel Moldt und Frank Wienberg

Anwendungen für verteilte Systeme wie das Internet, in denen nicht nur das Verhalten, sondern auch die Struktur Dynamik aufweist, gewinnen heutzutage mehr und mehr an Bedeutung. Das Paradigma der Agentenorientierung (AO) kann zu deren Entwicklung herangezogen werden, besitzt aber noch keine einheitliche theoretische Grundlage, und es herrscht nicht einmal Einigkeit über das Konzept des Agenten.

Es ist geplant, zu dieser Themenstellung ein Projekt einzurichten, das im folgenden genauer beschrieben wird. Die Formalisierung von Agentenkonzepten mit der Technik der Petrinetze soll als eine allgemeine theoretische Fundierung der Agentenorientierung untersucht werden. Um dynamische Systemstrukturen modellieren zu können, sollen entsprechende Konzepte auf Seiten der Petrinetze erweitert oder neu geschaffen werden, u. a. durch Definition von Netzen mit Marken, die wiederum aus Petrinetzen bestehen können.

Solche erweiterten Netzklassen und verschiedene zu untersuchende Phänomene der Agentenorientierung wie Mobilität, Autonomie und Intelligenz sollen im Projekt sowohl theoretisch als auch praktisch aufeinander abgestimmt werden, woraus schrittweise eigene Konzepte und Definitionen für Agenten(-systeme) entwickelt werden. Die für klassische Petrinetze bekannten Verfahren zur Modellierung, Validierung und Verifikation und die Konzepte der Agentenorientierung sollen soweit möglich auf die neuen Netzklassen übertragen, verbessert und anhand von Beispielen und Testanwendungen projektbegleitend praktisch erprobt werden.

Dienstag, 2. Dezember 1997, 14 Uhr c.t.

Spezifikation mit zyklischen Ordnungen

(zweiter Teil des Vortrags)

Mark-Oliver Stehr

Partielle zyklischen Ordnungen eignen sich zur abstrakten Spezifikation von deterministischen, nebenläufigen Systemen. Als Systemmodell verwenden wir sichere und lebendige Synchronizationsgraphen. Synchronizationsgraphen sind Petri-Netze ohne verzweigte Stellen. Verschiedene Begriffe der Implementierbarkeit werden im Vortrag betrachtet. Interessanterweise ist nicht jede zyklische Ordnung als Synchronizationsgraph implementierbar. Andererseits gibt es zyklische Ordnungen die durch verschiedene Synchronizationsgraphen implementiert werden können. Vorgestellt werden die Zusammenhänge zwischen Implementierbarkeit, Globaler Orientiertheit, (endlichen) Dichteeigenschaften und Uhrzyklendarstellungen.

Dienstag, 25. November 1997, 14 Uhr c.t.

ANNOTATIONES DE RATIONIBUS CRYPTOLOGIAE

Faktorisierungsmethoden (I)

Safuat Hamdy

Die Faktorisierung von Zahlen ist eine der ältesten bekannten mathematischen Probleme, bereits im antiken Griechenland hat man sich damit befaßt. Die Attraktivität dieses Problems geht nicht zuletzt auf das Theorem über eindeutige Zerlegung von ganzen Zahlen zurück, das bereits von Euklid formuliert und bewiesen wurde; dieses Theorem wird auch als Fundamentaltheorem der Arithmetik bezeichnet. Es sagt aus, da� jede von Null verschiedene Zahl aus Z (oder auch Q) bis auf die Reihenfolge und das Vorzeichen eindeutig in Primfaktoren zerlegt werden kann. Dabei bleibt aber leider im Dunkeln, wie man diese Zerlegung (d.h. Faktorisierung) erhält. Hier hilft nicht einmal die Tatsache, daß man die Zerlegbarkeit zusammengesetzter Zahlen mit Hilfe von Tests, wie z.B. dem von Rabin und Miller, nachweisen kann.

Dienstag, 18. November 1997, 14 Uhr c.t.

Spezifikation mit zyklischen Ordnungen

Mark-Oliver Stehr

Dienstag, 28. Oktober 1997, 14 Uhr c.t.

Twistabschluß von Sprachfamilien

Julia Maas

Mit der Operation twist wurde von Jantzen eine Operation auf Sprachen definiert, die u.a. zu einer neuen homomorphen Charakterisierung der rekursiv aufzählbaren Mengen führte. Inhalt der vorzustellenden Diplomarbeit ist es, einen Überblick über bereits bekannte Resultate zu geben und anschließend eine weitere Sprachfamilie auf ihren Abschuß unter der Operation twist hin zu untersuchen. Unterschiede zu der Arbeit von Jantzen - sowohl in der Zielsetzung als auch bei den Ergebnissen - ergeben sich dadurch, daß die Sprachfamilien mit Hilfe anderer Generatoren erzeugt werden. Dazu wird mit der Charakterisierung durch umkehrbeschränkte partially blind Mehrzählerautomaten gezeigt, daß die Familie M(aⁿbⁿ) twistabgeschlossen ist. Hieraus folgt, daß das kleinste, von der Sprache { aⁿbⁿ : n >= 0 } erzeugte twistabgeschlossene Trio nur rekursive Mengen enthält; dies unterscheidet sich zu dem Resultat von Jantzen, nach dem die Familie der rekursiv aufzählbaren Sprachen das kleinste twistabgeschlossene volle Trio bildet, das den Generator { w c w^rev fuer w in {a,b}^* } enthält.

> Veranstaltungen > Frühere Veranstaltungen > Lehre TGI

Letzte Änderung: 17:40 19.05.2011

Impressum