Tätigkeitsbericht 1993

Arbeitsbereich Prof. Dr. Wilfried Brauer

Theoretische Informatik und Grundlagen der KI (TIGKI)
Schwerpunktthema: Parallelverarbeitung

Fakultät für Informatik
Technische Universität München
Briefadresse: D-80290 München 2
Frachtadresse: Arcisstr. 21, D-80333 München 2

Telefax: +49-89-2105-8207, +49-89-2105-8483




Inhaltsverzeichnis






Mitglieder

Professoren

Prof. Dr. Wilfried Brauer
Prof. Dr. Klaus-Jörn Lange
Prof. Dr. Wolfgang Reisig, bis 30.6.93, danach Humboldt-Universistät Berlin

Wissenschaftliche Mitarbeiter

Dieter Barnard Doktorand (bei Siemens)
Dr. Jörg Desel wiss. Assistent bis 31.8.93
Martin Eldracher wiss. Angestellter
Dr. Robert Gold wiss. Angestellter
Dominik Gomm wiss. Angestellter, vom 5.6. bis 4.10.93 im Erziehungs-Urlaub
Andreas Heise wiss. Angestellter
Dr. Daniel Hernández wiss. Angestellter
Markus Holzer wiss. Angestellter
Dr. Birgit Jenner wiss. Assistentin, seit 7.7.92 im Erziehungsurlaub, ab 1.10.92 Forschungsaufenthalt am Dept. L.S.I. der Universitat Politecnica de Catalunya in Barcelona, Spanien mit Habilitationsstipendium der DFG
Dr. Astrid Kiehn wiss. Angestellte
Margit Kinder wiss. Angestellte
Ekkard Kindler wiss. Angestellter
Dr. Manfred Kunde Oberassistent, beurlaubt zu einer Vertretungsprofessur in Passau vom 1.4. bis 30.9.93
Angelika Mader wiss. Angestellte
Rolf Niedermeier wiss. Angestellter
Peter Rossmanith wiss. Angestellter
Dr. Jürgen Schmidhuber Oberassistent, seit 1.10.93
Oliver Schoett, PhD Akad. Rat a. Z., bis 31.5.93
Rolf Walter wiss. Angestellter, bis 31.8.93
Gerhard Weiß wiss. Angestellter

Sekretärinnen

Ingeborg Biberger-Karl
Paula Grylka

Studentische Hilfskräfte

Boris Baginski Projektbezogene Programmierarbeiten (NERES), seit 16.10.93
Till Brychcy Projektbezogene Programmierarbeiten (NERES)
Thomas Erlebach Implementierungsarbeiten im Rahmen des PRONTO-Projektes (SFB 0342, TP A4), seit Okt. 93
Thomas Feiner Programmierarbeiten in Scheme, seit 01.11.93
Rolf Großmann Softwarebetreuung (TeX, gcc), Hardwarebetreuung
Viola Krings Literaturbeschaffung und -verwaltung, Textverarbeitung, Büroorganisation
Gerd Pauli Hard- und Softwarebetreuung (Unix, Backups)
Markus Peisker Implementierung eines Petrinetztools
Doris Reisenauer Literaturbeschaffung und -verwaltung, Textverarbeitung, organisatorische Tätigkeiten
Dirk Rodemer Softwarebetreuung (email)
Peter Staffansson Bibliotheksrecherche, Texterstellung und Zusammenstellung des Petri Net Newsletters, seit 15.2.93

Gäste

30.6.93 B. Fritzke (ICSI, Berkeley)
Überwachtes Lernen mit wachsenden Zellstrukturen
15.7.93 A. Mukerjee (ITT, Indien)
Ambiguous geometric models
20.2. - 24.2.93 Peter van Emde Boas (Universität Amsterdam)
Applications of the logic of belief dependence
22.2. - 24.2.93 Juhani Karhumäki (Universität Turku)
Finite automata computing real functions
27.2. - 3.3.93 Martin Beaudry (Univ. de Sherbrooke)
The (exotic) circuit evaluation problem
30.9. - 6.10.93 Torben Hagerup (Max-Planck-Institut für Informatik, Saarbrücken)
Fast deterministic approximate and exact parallel sorting
12.1.93 Niki Schraudolph (SALK Institute, San Diego)
Temporal difference learning of position evaluation in the game of Go

Lehrbeauftragte

Dr. H. Geiger, Geiger Neuroconsulting
Dr. M. Payer, Siemens ZFE, München
Dr. D. Taubner, sd&m, München






Drittmittel

Sonderforschungsbereich 342, Teilprojekt A3 SEMAFOR (Spezifikations-, Entwurfs- und Analyseformalismen)

Sonderforschungsbereich 342, Teilprojekt A4 KLARA (Klassifikation und Parallelisierung durch Reduktionsanalyse)

Sonderforschungsbereich 342, Teilprojekt Y1 (Kooperationsprojekt mit der Humboldt-Universität, Berlin)

DFG-Projekt im Rahmen des SPP Datenstrukturen und effiziente Algorithmen: Entwurf und Analyse von Datentransport- und anderen grundlegenden Algorithmen für Prozessornetzwerke (Ku 658/1-3)

Kooperation mit dem ZFE F2 der Siemens AG auf dem Gebiet der Verifikation paralleler Prozesse.

ESPRIT BRA Project No 6067 CALIBAN: Causal Calculi Based on Nets.

ESPRIT BRA Working Group No 3166 ASMICS: Algebraic and Syntactic Methods in Computer Science.

BMFT Verbundprojekt NERES: Neuronale Regelung und Steuerung für Industrieroboter (FKZ 01 IN 102 B/0)

DAAD-ARC: An Algebraic Theory for Distributed Systems: Kooperation mit der University of Sussex

DFG Projekt Br609/5-1: Verteiltes maschinelles Lernen in Mehragentensystemen






Darstellung der Forschungsvorhaben

Projekte

BMFT Verbundprojekt NERES:
``Neuronale Regelung und Steuerung für Industrieroboter''
(FKZ 01 IN 102 B/0) (Leitung: Brauer, Hernández)

Allgemeine Projektbeschreibung:
Das vom BMFT auf vier Jahre finanzierte Verbundprojekt NERES (Partner: Siemens AG, München; DLR, Oberpfaffenhofen; Universität Dortmund) strebt auf subsymbolischem Niveau eine Symbiose zwischen Sensorik und Aktuatorik einerseits und neuronaler Signalverarbeitung und Steuerung andererseits an. Allerdings sollen auch KI-Techniken für solche Fälle einbezogen werden, die eine über das Subsymbolische hinausgehende robuste Wissensrepräsentation benötigen, wie z.B. bei der Raumrepräsentation. Die an der TU bearbeiteten Teilprojekte konzentrieren sich auf lernende neuronale Netzwerke in dynamischen Umgebungen, die zur Trajektorienplanung eingesetzt werden können, insbesondere unter Ausnutzung hierarchischer Strukturen. Weiterhin werden symbolische qualitative Ansätze zur Darstellung zeitlichen und räumlichen Wissens untersucht, die als gemeinsamer repräsentationstheoretischer Rahmen zur Entwicklung spezieller neuronaler Anwendungen dienen können.

Im folgenden werden die im dritten Jahr bearbeiteten Aspekte des Projektes zusammengefaßt:

Neuronale Subzielgenerierung (Eldracher, Baginski, Schittenkopf)
Die in 1992 erstellte Robotersimulationsumgebung wurde zur Generierung von Subzielen in zwei- und dreidimensionalen Umgebungen eingesetzt. Dabei kamen verschiedenen Konzepte zur Erzeugung der Subziele zum Einsatz: Backpropagation für jeweils ein einzelnes Subziel, oder für jeweils eine ganze Umgebung und inkrementelles Lernen bekannter Subziele. Dabei wurde für die teilweise sehr großen Netzwerke ein Pruning-Algorithmus mit integriert, der die Ergebnisse verbessern und die Netztopologie vereinfachen kann.

Planung einzelner Pfade (Eldracher, Staller, Birnbacher, Eisele)
Versuche mit einem einfacheren Modell aus adaptiven Kritiker und Steuernetzwerk zeigten, daß es ohne Speicher sehr schwierig ist, einzelne Pfade zu planen. Deshalb wurde mit gutem Erfolg eine Kombination aus Reinforcement-Lernen mit TD-Verfahren und einem CMAC als Speicher durchgeführt.

Revisionsmechanismus für qualitative Constraintnetze (Hernández, Feiner)
Das Entfernen einer Relation aus einen Constraintnetz muß alle aus dieser Relation abgeleiteten (propagierten) Konsequenzen ebenfalls revidieren. Dies erfordert eine Modifikation des Propagierungsalgorithmus, so daß die in der Ableitung neuer Constraints involvierten Relationen festgehalten werden. In der Regel wird diese Information in einem getrennten ``Abhängigkeitsnetz'' verwaltet, welches aus Knoten, die den Kanten des Constraintnetzes entsprechen, und Kanten, die die Abhängigkeitsstruktur darstellen, besteht. Auf dieser Struktur operiert ein Abhängigkeitsverwaltungsalgorithmus, welcher die Konsistenz eines Netzes ohne den Mehraufwand (und evtl. Informationsverlust) einer vollständigen erneuten Propagierung wiederherstellt.

Neuronale Trajektorienplanung (Kinder, Brychcy, Pietruscha, Sundermann; Gramlich (DLR) )
Schwerpunkt des Forschungsvorhabens ist die Trajektorienplanung für sechsgelenkige Manipulatoren in Umgebungen mit Hindernissen. Die im erstellten Planungstool verwirklichte Methode ist die der Planung durch generalisierende Trajektorienspeicherung. Dabei wurden Aspekte der klassischen KI mit solchen der Neuronalen Netze verknüpft. Soweit möglich wurden auch rein mathematische Ansätze integriert bzw. Möglichkeiten hierfür erarbeitet. Laufende Arbeiten an einer verteilten Kodierung von reellwertigen Ausgabewerten dienen einer weiteren Verbesserung der Generalisierungsfähigkeit des Planungssystems. Ferner wurden numerische Optimierungsverfahren auf das Lernen in Neuronalen Netzen übertragen.

Fuzzy Logik mit neuronalen Netzen (Kinder, Bücherl; Geiger (Geiger Neuroconsulting), Pfalzgraf (RISC Linz) )
Zur qualitativen Beschreibung von Trajektorien, sowie auch allgemeiner im Gebiet der Prozeßführung, bietet sich oft eine Formalisierung von Wissen durch Fuzzy Logik an. Derzeit wird die Grundlage der Verknüpfung derartiger Formalisierungen mit Neuronalen Netzen geschaffen. In enger Zusammenarbeit mit dem RISC Linz entsteht dort eine benutzerfreundliche Oberfläche zur Beurteilung einer solchen Verknüpfung und insbesondere des Lernerfolges.

SFB 0342 Teilprojekt A3 ``Spezifikations-, Entwurfs- und Analyseformalismen''
Leitung: Brauer, Kröger, Reisig

Insbesondere
- soll ein Satz von Konzepten und Methoden zur formalen Behandlung verteilter Systeme entwickelt werden. Vor allem sollen dabei Aspekte der Kausalität und der Lokalität berücksichtigt werden.
- soll der bisher im Rahmen des SFB 0342/A3 entwickelte Editor für High Level Petrinetze um eine Simulationskomponente erweitert werden. Voraussetzung dafür ist unter anderem ein Softwaremodul zum Finden von Normalformen und Lösen von Gleichungen für algebraische Spezifikationen,
- soll aufbauend auf den Arbeiten über verhaltenserhaltende Abbildung auf Petrinetzen und unter Zuhilfenahme von Techniken aus der Kategorientheorie, ein formales Modularisierungs- und Parameterisierungskonzept entwickelt werden, das gestattet, komplexe Systeme aus Teilspezifikationen zusammenzusetzen und Teillösungen wiederzuverwenden. Dabei soll die Semantik und die Eigenschaften (z.B. Invarianz, Erreichbarkeit) des Gesamtsystems aus denen der Teilnetze berechenbar sein.

Verifikation von sequentiellen und nichtsequentiellen Systemen
(Zusammenarbeit mit Siemens ZFE)

Brauer; Cuellar, Barnard (Siemens); Kiehn, Mader
Entwicklung neuer effizienter symbolischer Methoden auf der Basis von binären Entscheidungsdiagrammen; Weiterentwicklung von Methoden des model checking, insbesondere Untersuchung des modalen µ-Kalküls.

DAAD-ARC: An Algebraic Theory for Distributed Systems

Brauer, Kiehn; Hennessy und Mitarbeiter (University of Sussex, Brighton)
Ziel des Projektes ist die Entwicklung einer algebraischen Theorie, die es aufsetzend auf Prozeßalgebren erlaubt, strukturelle Aspekte wie Lokalität, Nebenläufigkeit und Modularität zu beschreiben und zu analysieren. Hierzu wurden einerseits für bereits bestehende semantische Äquivalenzen Beweissysteme entwickelt, andererseits Entscheidbarkeitsfragen in Angriff genommen.

SFB 0342 Teilprojekt A4 ``Klassifikation und Parallelisierung durch Reduktionsanalyse: KLARA'' (Leitung: Brauer, Lange)

Lange, Niedermeier
Untersuchungen im Hinblick auf Kommunikationsstrukturen von parallelen Registermaschinen (PRAM's) wurden fortgesetzt und ausgebaut. Zudem wurde als neues Maschinenmodell die Index-PRAM eingeführt und im Rahmen der klassischen parallelen Komplexitätstheorie charakterisiert.

Niedermeier, Rossmanith
Hertrampfs lokal definierte Akzeptanztypen wurden modifiziert, um im Rahmen dieses Modells auch eine Charakterisierung insbesondere eindeutiger Komplexitätsklassen und Komplexitätshierarchien zu erhalten.

Niedermeier, Rossmanith
Für Concurrent Read, Exclusive Write PRAM's wurde gezeigt, daß gleichzeitiges Lesen und Schreiben in verschiedene Zellen des globalen, gemeinsamen Speichers eine Beschleunigung gegenüber herkömmlichen CREW-PRAM's ermöglicht. Analoge, sogar allgemeinere Ergebnisse konnten auch für Concurrent Read, Owner Write PRAM's erhalten werden. Außerdem wurden für die beiden Modelle auch verbesserte untere Schranken bewiesen.

Kunde, Niedermeier, Rossmanith
Es wurden schnelle Routing- und Sortieralgorithmen für gitterartig verbundene Prozessornetzwerke, die zusätzlich Diagonalverbindungen enthalten, entwickelt. Dabei konnten deutlich bessere Ergebnisse als für Gitter ohne Diagonalverbindungen erzielt werden.

DFG Projekt Br609/5-1 ``Verteiltes maschinelles Lernen in Mehragentensystemen'' (seit 10/93):

Brauer, Weiß
Entwicklung von Problemlösungs- und Planungsverfahren für Mehragentensysteme, die auf Methoden des verteilten maschinellen Lernens basieren.

Brauer, Weiß, Turck
Entwurf adaptiver Verfahren für statisches Scheduling in Mehragentensystemen.

ESPRIT Projekt CALIBAN (WG EP 6067 der EU) (Leitung: Brauer, Desel)

Brauer, Desel, Kindler, Reisig; Vogler (Uni Augsburg)
CALIBAN ist das Nachfolgeprojekt von DEMON, an dem die Technische Universität München ebenfalls beteiligt war. Inhalt und Ziel von CALIBAN ist die Integration und Kombination kausalitätsbasierter Modelle für nebenläufige Systeme (wie Petrinetze) und algebraisch orientierter Modelle (wie Prozeßalgebren). Beiträge der TU München sind insbesondere
- Ausarbeitung und Verallgemeinerung von Ergebnissen aus dem Bereich der Strukturtheorie. Ein Schwerpunkt sind dabei Arbeiten zu free-choice Netzen, die im Rahmen von DEMON entstanden sind.
- Verwendung algebraischer Methoden zur Erreichbarkeitsanalyse in Netzen. Es wurde gezeigt, daß analog zu bekannten linear-algebraischen Analysemethoden (Stellen-Invarianten) die Betrachtung von Restklassen (Modulo-Stellen- Invarianten) zu schärferen Aussagen führt.
- Eine Charakterisierung des Grenzwertes von Splitting-Äquivalenz. Zwei Netze sind splitting-äquivalent, wenn, für ein gegebenes n, die Zerlegung der Aktionen in n Teilaktionen sprachen-äquivalente Netze ergibt. Für wachsendes n werden die erzeugten Äquivalenzen immer feiner, ihr Grenzwert kann durch die sogenannte swap-Äquivalenz charakterisiert werden. Weitere Eigenschaften dieser swap-Äquivalenz wurden untersucht.
- Eine temporale Logik, die Verteiltheit von Systemen in besonderem Maß berücksichtigt. Diese Logik wird über kausalen Abläufen von Netzen interpretiert. Theoretische Untersuchungen betrachten Eigenschaften derartiger Abläufe im Vergleich zu Eigenschaften klassischer sequentieller Systemabläufe. Einige Fallstudien wurden mit Hilfe dieses Formalismus durchgeführt.
- Das allgemeine Jahrestreffen des Projektes CALIBAN wurde im September 1993 in Fischbachau/Obb. organisiert.

Mit dem Wechsel von Prof. Reisig und Dr. Desel an die Humboldt-Universität zu Berlin wurde das Projekt hälftig geteilt.

Grundlagen und Anwendungen neuronaler Netze
(Zusammenarbeit mit Siemens ZFE, Kratzer Automatisierung, Institut für Medizinische Psychologie der Ludwig-Maximilians-Universität München, Lehrstuhl für Nachrichtentechnik der Technischen Universität München und GSF - Forschungszentrum für Umwelt und Gesundheit)

Brauer; Schürmann, Deco, Hollatz, Ormoneit, Schittenkopf, Tresp (Siemens); Engelbrecht, Arnoldi, Waschulzik, Däschlein, Eberhard, Ehrlicher, Grothe, Nöhmeier, Spickhoff (GSF); Geiger (Geiger Neuroconsulting); Butz, Noack, Mayer, Sturm (Kratzer Automatisierung)

In Zusammenarbeit mit Siemens (Dissertationen, Diplomarbeiten) werden Anwendungen neuronaler Netze auf verschiedenartige Probleme untersucht: Zeitreihenanalysen, Vorhersage von Wechselkursen/Börsenkursen; induktives Lernen, Integration von unsicherem Regelwissen, Anwendung auf Schlußfolgerungsverfahren in verschiedenen Bereichen (rechtliche Fragen, Vorhersage von Immobilienpreisentwicklungen, Robotersteuerung), Untersuchung von Zusammenhängen mit statistischen Verfahren und Fuzzy-Control-Systemen.

In Zusammenarbeit mit der Arbeitsgruppe Anwendersysteme des MEDIS-Instituts des Forschugszentrums für Umwelt und Gesundheit (GSF) wurde eine Etnwicklungsmethodik für die anwendungsspezifische Konstruktion von strukturierten neuronalen Netzen entworfen und an Hand von Projekten in den Bereichen Prognose von Lymphkontenmetastasen bei Magenkarzinomen, Analyse von epidemiologischen Studien, Analyse von vorverarbeiteten EKG's, Erkennung von vereinzelten Objekten und Segmentierung von Computertomogrammen evaluiert.

In Zusammenarbeit mit der Firma Kratzer Automatisierung München wurden Untersuchungen zur sequentiellen rückgekoppelten Hypothesenbildung in Single-Spike-Modellen und zur Anwendung von ausgewählten Lernverfahren zur Spracherkennung durchgeführt. Ferner wurden Verfahren zur Darstellung und assoziativen Speicherung statistischer (algebraischer) Funktionen in neuronalen Netzen entwickelt und sowohl qualitativ als auch quantitativ analysiert.

Weitere Forschungsvorhaben

Barnard
Untersucht wurden Methoden und Algorithmen zur Verifikation von parallelen und verteilten Systemen, insbesondere Erweiterungen des Model Checking-Verfahrens für einen bei Siemens entwickelten Formalismus mit unendlichen Zustandsräumen und UNITY ähnlicher temporaler Logik.

Brauer, Weiß, Stutz, Kirchmaier
Untersuchung der Schnittstelle von künstlichen Neuronalen Netzen und evolutionären Algorithmen.

Brauer, Weiß, Wirth
Entwicklung von organisationellen Lernverfahren für regelbasierte Systeme, insbesondere für die spezielle Klasse der sog. classifier systems.

Damm (Uni Trier), Holzer
Es wurde eine neues nichtuniformes Berechnungsmodell, die sogenannte programmierte Turingmaschine, eingeführt. Im Falle eines Speicherplatzbedarfes von O(log n) stimmt das nichtuniforme Modell der programmierten Turingmaschine mit dem Nichtuniformitätsbegriff von Karp und Lipton überein. Es konnte die Äquivalenz platzbeschränkter programmierter Turingmaschinen und Verzweigungsprogrammen mit beschränkter Weite gezeigt werden. Darüberhinaus wurde gezeigt, daß nichtuniforme nichtdeterministische Klassen mit o(log n) Speicherplatz unter Komplement abgeschlossen sind. Zum Beweis wurde die Technik des induktiven Zählens auf Verzweigungsprogramme übertragen.

Damm (Uni Trier), Holzer, Lange, Rossmanith
Die Ergebnisse zur komplexitätstheoretischen Klassifizierung der D0L Sprachen wurden verbessert. Es gelang eine verbesserte obere Schranke für das D0L Membership Problem anzugeben. Es wurde gezeigt, daß D0L Sprachen durch AC0 Schaltkreise mit fester Tiefe erkennbar sind.

Eldracher, Dechentreiter
Mit Hilfe wachsender Zellstrukturen wurden inverse Modellierungen für zwei- und dreigelenkige Roboter erlernt. Im Gegensatz zu früheren Arbeiten wurde Hindernisse, die eine stetige Modellierung unmöglich machen, in die Umgebung eingebracht. Zudem wurde der Arbeitsraum des Roboters nicht auf ein Teilgebiet der erlaubten Gelenkwinkelstellungen beschränkt.

Eldracher, Huber
Zur effizienten Speicherung von Trajektorien können jeweils die relevanten Teilschritte allein gespeichert werden. Zur Abfrage des Speichers muß allerdings bekannt sein, zu welchem Zeitpunkt diese relevanten Teilschritte angewandt werden müssen. Es erwies sich als wesentlich schwieriger die Zeitrepräsentation mitzuspeichern, als die Teilschritte selbst.

Gold
Die Untersuchung von Semantiken für Petrinetze, die das Ein-/Ausgabeverhalten beschreiben, wurde fortgesetzt. Es wurde eine Spursemantik definiert, die das Terminierungsverhalten beschreibt. Sie ist kompositional bzgl. Parallelkomposition mit asynchroner Kommunikation und vollständig abstrahierend bzgl. einer Basissemantik, die für jede Eingabe die Ausgabe und eine Terminierungsinformation angibt.

Gomm
Erstellung einer Dissertation mit dem voraussichtlichen Thema: `` Petrinetzbasierte Beweismethoden für verzögerungsabhängige Schaltungen''

Heise
Erstellung einer Dissertation mit dem voraussichtlichen Thema: ``Parameterisierungs- und Modularisierungskonzepte für High Level Petrinetze''.

Hernández, Högg, Schwarzer
Qualitative Darstellung von Formen: Es wurde ein Modell zur qualitativen Beschreibung von Grundformen (Högg, 1993, Diplomarbeit) sowie darauf basierend ein System zur qualitativen Beschreibung zusammengesetzter Formen entwickelt (Schwarzer, 1993, Diplomarbeit). Das Modell ermöglicht größen- und lageinvariante Formbeschreibungen. Bei zusammengesetzten Objekten werden die einzelnen Komponenten durch Relationen in ihrer Lage fixiert und ihre relative Größe qualitativ bestimmt. Auch Aussparungen und intrinsische Richtungen sind beschreibbar. Ein Matching-Prozeß erlaubt einen Vergleich von Beschreibungen hinsichtlich verschiedener Ähnlichkeitskriterien.

Holzer
Das Leerheitsproblem für alternierende endliche Automaten mit unärem Eingabealphabet konnte als PSPACE-vollständig nachgewiesen werden. Im Zusammenhang mit alternierenden endlichen Automaten wurden verschiedene Probleme wie Inklusion, Segment Äquivalenz, Universalität, Äquivalenz, Endlichkeit, Closeness und Sparseness komplexitätstheoretisch klassifiziert. Desweiteren wurden die funktionalen Probleme Census, Ranking und Maxword untersucht. Es zeigte sich, daß diese Probleme für polynomielle Zählklassen wie P und opt-P vollständig sind.

Holzer, Lange
Die Untersuchung zur Charakterisierung symmetrischer Komplexitätsklassen wurde fortgesetzt. Insbesondere konnte durch die operatorentheoretische Charakterisierung von SYMSPACE(log n) eine Orakelhierarchie definiert, und deren strukturelle Eigenschaften untersucht werden. Weitere Ergebnisse konnten im Bereich der Relativierung, in Bezug auf operatorentheoretische Charakterisierung von Komplexitätsklassen, erzielt werden.

Holzer, Lange
Die Ergebnisse zur Komplexität linearer Sprachen wurden verfeinert. Untersuchung anderer linearer Sprachfamilien, wie z.B. den linearen Index-Sprachen, wurden durchgeführt.

Holzer, Rossmanith
Es wurde ein Literaturstudium über die Verwendung von Fibonacci-Zahlen im Bereich der formalen Sprachen durchgeführt.

Kiehn
Die Untersuchungen zu Beweissystemen für sogenannte non-interleaving Äquivalenzen wurden abgeschlossen. Als Ergebnis konnten Beweissysteme entwickelt werden, die bereits vorliegende, aber nur für eingeschränkte Prozeßmengen gültige Beweissysteme kanonisch erweitern.

Kunde
Die Untersuchung von schnellen deterministischen Paket-Routing-Algorithmen und Sortieralgorithmen auf Gittern wurde fortgesetzt. Dabei zeigte sich, daß sich mit Hilfe der bei unterschiedlichen Problemstellungen gewonnenen Methoden und Beweismitteln (Informationssammeln durch Sortieren, geordnete Informationsverteilung, Lastbalancierung, überlapptes Arbeiten) Algorithmen entwerfen lassen, deren Schrittzahl die einfache Bisektionsschranke asymptotisch erreicht. Die dabei gewonnenen Methoden lassen sich darüber hinaus auf Netze beliebiger Struktur anwenden.
Untersuchungen von Modellen zur Lastbalancierung führten zu ersten Resultaten auf Ringen mit intelligenten Speichern. Eine Erweiterung auf zweidimensionale Tori scheint ebenfalls gute Resultate zu bringen.

Lange, Rossmanith
Untersuchungen über PRAMs mit exponentieller Prozessoranzahl und ihren Beziehungen zu eindeutigen Klassen und Hierarchien, ähnlich der polynomiellen Hierarchie, sowie zu Schaltnetzen.

Schmidhuber, Hochreiter, Prelinger, Heil, Storck
Neuronale Netze, (algorithmische) Informationstheorie und Redundanz:
Mit Hilfe geeigneter formaler Definitionen der Begriffe ``Einfachheit'', ``Informationsgehalt'' und ``Redundanzarmut'' sollen existierende Lernalgorithmen für künstliche Neuronale Netze (KNN) verbessert (d.h. beschleunigt und ihre Generalisierungsfähigkeit erhöht) werden. Zwei Hauptrichtungen sollen verfolgt werden: Adaptive ``Vereinfachung'' der (1) Netzwerkeingaben bzw. der (2) Netzwerke selbst. ``Vereinfachung'' ist dabei entweder im Sinne der klassischen Informationstheorie oder im Sinne der algorithmischen Informationstheorie gemeint.
Etwas präziser ausgedrückt:
Zu (1): Tragen Eingaben aus der Umgebung redundante Information (was sie in reellen Anwendungen immer tun), sollen durch neue unüberwachte Lernalgorithmen automatisch ``einfache'', im informationstheoretischen Sinn redundanzarme und kompakte Eingabebeschreibungen extrahiert werden. Letztere sind für zahlreiche Anwendungen wesentlich erfolgsversprechender (in Bezug auf Lernperformanz) als die ``rohen'' Eingabedaten.

Zu (2): Gemeint ist die automatische Auffindung von Netzwerkmodellen, die zwar einerseits für alle Trainingssituationen geeignet sind, deren kürzeste Beschreibungen aber andererseits (im informationstheoretischen Sinne) kompakt und redundanzarm sind. Dies sollte sowohl schnellere Lernverfahren als auch verbesserte Generalisierungsfähigkeit ermöglichen.






Veröffentlichungen

Álvarez, C.; Jenner, B.: A very hard log-space counting class. - In: Theoretical Computer Science, Volume 107, 1993, S. 3-30

Barnard, D.; Mader, A.: Model checking for the modal µ-calculus using Gauss elemination. Technical Report, Aug. 1993

Bauer, F.L.; Brauer, W.; Schwichtenberg, H.: Logic and algebra of specification. Springer-Verlag, Berlin, 1993.

Boudol, G.; Castellani, I.; Hennessy, M.; Kiehn, A.: Observing localities. Theoretical Computer Science 114, 1993, S. 31-61.

Brauer, W.: Distributed action systems. - In: Logic and Algebra of Specification. Bauer, F.L.; Brauer, W. (eds.). Springer-Verlag, 1993, S. 1-30.

Brauer, W.: KI auf dem Weg in die Normalität. - In: Künstliche Intelligenz, 7. Jahrgang, Sonderheft August 1993, S. 85-91.

Brauer, W.; Brauer, U.: Further remarks on the jeep problem. - In: Karmann, A.; Mosler, K.; Schader, M.; Uebe, G. (eds.): Operation Research `92. Physika-Verlag, Heidelberg, 1993, S. 109-111.

Butz, D.; Noack, K.; Brauer, W.: Representation of real-valued functions by a three-layered artificial neural network with topologically ordered input and output units. - In: Gielen, St.; Kappen B. (eds.): Proceedings of the Int. Conference on Artificial Neural Networks, ICANN `93, Amsterdam 13.-16.9.1993, Springer-Verlag, Berlin, 1993, S. 818--821.

Damm, C.; Holzer, M.; Lange, K.-J.; Rossmanith, P.: Deterministic 0L languages are of very low complexity: D0L is in AC0 - In: Proceedings of the Conference Developmentals in Language Theory 1993, Turku, Finland, July 12-14, 1993

Desel, J.: Regular marked Petri nets - erscheint In: Proceedings of Graph - Theoretic Concepts in Computer Science (WG 93), Juni 1993, Lect. Notes in Computer Science, Springer--Verlag, 1993

Desel, J.; Esparza, J.: Reachability in cyclic extendet free-choice systems. - In: Theoretical Computer Science 114, 1993, S. 93-118.

Desel, J.; Esparza, J.: Structure theory of free choice systems. - In: Best, E. (ed.): Design Methods Based on nets, Final Report, GMD-Studien Nr. 217, S. 113-129, Gesellschaft für Mathematik und Datenverarbeitung, 1993

Desel, J.; Esparza, J: Shortest paths in reachability graphs - In: M. Ajmone Marsan (ed.): Proceedings of the XIV Int. Conference on Applications and Theory of Petri Nets, Chicago, Juni 1993, S. 224-241, Springer-Verlag, 1993. (Lect. Notes in Computer Science; 691)

Desel, J.; Radola, M.-D.: Proving non-reachability by modulo-place-invariants. Informatik-Berichte der Humboldt-Universität zu Berlin, Nr. 24, 1993

Desel, J.; Reisig, W.: The synthesis problem of Petri nets. - In: Enjalbert, P.; Finkel, A.; Wagner, K. (eds): Proceedings of STACS 93, X Annual Symposium of Theoretical Aspects of Computer Science, Würzburg, Februar 1993, S. 120-129, Springer-Verlag, 1993. (Lect. Notes in Computer Science; 665)

Eder, K.; Geiger, H.; Brauer, W.: A neurophysiologically motivated neural network model and its application to the superpostion problem. - In: Gielen, St.; Kappen, B. (eds.): Proceedings of the Int. Conference on Artificial Neural Networks, ICANN `93, Amsterdam 13.-16.9.1993, Springer-Verlag, Berlin, 1993, S. 482--485.

Eldracher, M.: Topologically distributed encoding to facilitate learning. - In: Journal of Systems Engineering, Heft 3, 1993, Springer-Verlag London Limited, S. 110-119.

Eldracher, M.; Baginski, B.: Hierarchical Planning Using Neural Subgoal Generation. - In: Proceedings of IEEE SMC'93, Okt. 1993

Eldracher, M.; Baginski, B.: Neural subgoal generation using backpropagation. - In: George G. Lendaris, Stephen Grossberg und Bart Kosko (eds.): World Congress on Neural Networks. Lawrence Erlbaum Associates, Inc., Publishers, Hillsdale, Juli, 1993, S.III-145-III-148.

Gold, R.: Datenfluß semantiken für Petrinetze. Dissertation. München: Technische Universität München, Fakultät für Informatik, 1993.

Gomm, D.; Kindler, E.: Causality based proof of a distributed shared memory system. - In: Bode, DalCin (eds.): Parallel Computation Architectures: Theory, Hardware, Software, Applications. Springer-Verlag, Berlin, 1993. (Lect. Notes in Computer Science; 732)

Gomm, D.; Kindler, E.; Paech, B.; Walter, R: Compositional liveness properties of EN-systems. - In: M. Ajmone Marsan (ed.): Proceedings of 4th Int. Conference on Application and Theory of Petri Nets, Chicago, Juni 1993. Springer-Verlag, Berlin, S. 262-281. (Lect. Notes in Computer Science; 691)

Hernández, D.: Hybride und integrierte Ansätze zur Raumrepräsentation und ihre Anwendung. - In: Grundlagen und Anwendungen der Künstlichen Intelligenz. 17. Fachtagung für Künstliche Intelligenz. Humboldt-Universität zu Berlin, Sept. 1993. Hrsg.: O. Herzog u.a. Springer-Verlag, Berlin, 1993, S. 210-216. (Informatik Aktuell)

Hernández, D.: Maintaining qualitative spatial knowledge. - In: A. U. Frank et al (eds.): Spatial Information Theory. A Theoretical Basis for GIS. European Conference, COSIT'93. Marciana Marina, Elba Island, Italy, Sept. 1993. Springer-Verlag, Berlin, 1993, S. 36-53. (Lect. Notes in Computer Science; 716)

Hernández, D.: Reasoning with qualitative representations: Exploiting the structure of space. - In: N. Piera Carreté et al (eds.): Proceedings of the III IMACS Int. Workshop on Qualitative Reasoning and Decision Technologies - QUARDET'93, Barcelona, 16-18 June 1993. Barcelona: CIMNE, 1993, S. 493--502.

Hernández, D.; Zimmermann, K.: Default reasoning and the qualitative representation of spatial knowledge. München: Institut für Informatik, Technische Universität München, 1993 (Forschungsberichte Künstliche Intelligenz; FKI-175-93)

Hernández, D. (ed.): Proceedings des Workshops ``Hybride und integrierte Ansätze zur Raumrepräsentation und ihre Anwendung''. Im Rahmen der 17. Fachtagung für Künstliche Intelligenz vom 13.-16. Sept. 1993 an der Humboldt-Universität zu Berlin. München: Institut für Informatik, Technische Universität München, 1993 (Forschungsberichte Künstliche Intelligenz; FKI-185-93)

Holzer M.; Lange, K.-J.: On the complexities of linear LL(1) and LR(1) grammars - In: Z. Ésik (ed.): Proceedings of the 9th Int. Conference on Fundamentals of Computation Theory 1993, Szeged, Ungarn, Aug. 23-27, 1993. Springer-Verlag, Berlin, 1993, S. 299-308. (Lect. Notes in Computer Science; 710)

Kiehn, A.: Proof systems for cause based equivalences. - In: Tagungsband der MFCS '93., 1993, S. 547-556. (Lect. Notes in Computer Science; 711)

Kinder M.; Brauer, W.: Classification of Trajectories - Extracting Invariants with a Neural Network - In: Neural Networks, 1993, Volume 6, Number 7, S. 1011--1017

Kinder, M.; Brychcy, T.: A Neural Trajectory Storage, München: Institut für Informatik, Technische Universität München, 1993. (Forschungsberichte Künstliche Intelligenz; FKI-182-93)

Kinder, M.; Brychcy, T.; Brauer, W.: Neuronale Planung von Roboterbewegungen, - In: Handout Industriemesse SYSTEMS '93, Okt. 1993

Kinder, M.; Heindl, J.: Auch ein Roboter muß lernen, TUM Sonderreihe Forschung für Bayern, Nummer 6, 1993

Kinder, M.; Brychcy, T.: Theoretical issues concerning the representation of continuous-valued input and output data in neural networks, München: Institut für Informatik, Technische Universität München, 1993. (Forschungsberichte Künstliche Intelligenz; FKI-183-93)

Kindler, E.: Sicherheits- und Lebendigkeitseigenschaften: Ein Literaturüberblick. Interner SFB-Bericht 342/2/93 B, Dez. 1993.

Kindler, E.; Walter, R.: Rearranging problems. - In: Petri Net Newsletter 34, 1993.

Kunde, M.: Block gossiping on grids and tori: deterministic sorting and routing match the bisection bound. - In: T. Lengauer (ed.): Proceedings of the 1st Annual European Symposium on Algorithms - ESA 93, Bad Honnef, 30. Sept.--2. Okt., 1993. Springer-Verlag, Berlin, 1993, S. 272--283. (Lect. Notes in Computer Science; 726)

Kunde, M.: Packet routing on grids of processors. - In: Algorithmica 9, 1993, S. 32-46.

Lange, K.-J.: Complexity and Structure in Formal Language Theory. - In: Proceedings of the 8th Annual Conference Structure in Complexity Theory, Mai 1993, San Diego, California, 1993, S. 224-238.

Lange, K.-J.: Unambiguity of Circuits. - In: Theoretical Computer Science, Volume 107, 1993, S. 77-94.

Lange, K.-J.; Niedermeier, R.: Data-independences of parallel random access machines. - In: Shyamasundar, R. K. (ed.): Proceedings of the 13th Conference on Foundations of Software Technology and Theory of Computer Science, Bombay, India, Dezember 1993. Springer-Verlag, 1993, S. 104-113. (Lect. Notes in Computer Science; 761)

Niedermeier R.; Rossmanith, P.: On the power of reading and writing simultaneously in parallel computations. - In: Ng, K. W.; Raghavan, P.; Balasubramanian, N. V.; Chin, F. Y. L. (eds.): Proceedings of the 4th Int. Symposium on Algorithms and Computation, Hong Kong, December 1993. Springer-Verlag, 1993, S. 240-249. (Lect. Notes in Computer Science; 762)

Niedermeier, R.; Rossmanith, P.: Extended locally definable acceptance types. - In: P. Enjalbert et al. (eds.): Proceedings of the 10th Symposium on Theoretical Aspects of Computer Science, Würzburg, Febr. 1993. Springer-Verlag, Berlin, 1993, S. 473-483. (Lect. Notes in Computer Science; 644)

Quandt, K; Waschulzik, T.; Lewis, M.; Hörmann, A.; Engelbrecht, R; Brauer, W.: Evaluation of epidemiological data with neural networks. - In: George G. Lendaris, Stephen Grossberg und Bart Kosko (eds.): World Congresson Neural Networks. Lawrence Erlbaum Associates, Inc., Publishers, Hillsdale, Juli, 1993, S. I257-I260

Rossmanith, P.; Rytter, W.: Observations on log n time parallel recognition of unambiguous context-free languages. - In: Information Processing Letters 44, 1993, S. 267-272.

Schmidhuber, J. H.: A neural network that embeds its own meta-levels. - In: Proceedings of the Int. Conference on Neural Networks '93, San Francisco, IEEE, 1993.

Schmidhuber, J. H.: A self-referential weight matrix. - In: Proceedings of the Int. Conference on Artificial Neural Networks, Amsterdam, Springer, 1993, S. 446-451.

Schmidhuber, J. H.: An introspective network that can learn to run its own weight change algorithm. - In: Proceedings of the Int. Conference on Artificial Neural Networks, Brighton, IEEE, 1993, S. 191-195.

Schmidhuber, J. H.: Netzwerkarchitekturen, Zielfunktionen und Kettenregel. Habilitationsschrift, Institut für Informatik, Technische Universität München, 1993

Schmidhuber, J. H.: On decreasing the ratio between learning complexity and number of time-varying variables in fully recurrent nets, - In: Proceedings of the Int. Conference on Artificial Neural Networks, Amsterdam, Springer, 1993, S. 460-463.

Schmidhuber, J. H.: ``Neural'' redundancy reduction for text compression. - In: Neural Network World, Volume 3, Number 6, 1993, S. 849-853.

Schmidhuber, J. H.; Prelinger, D.: A novel unsupervised classification method. - In: Proceedings of the Int. Conference on Artificial Neural Networks, Brighton, IEEE, 1993, S. 91-96.

Schmidhuber, J. H.; Prelinger, D.: Unsupervised extraction of predictable abstract features. - In: Proceedings of the Int. Conference on Artificial Neural Networks, ICANN `93, Amsterdam, Springer, 1993, S. 601-604.

Schmidhuber, J. H.; Mozer, M. C.; Prelinger, D.: Continuous History Compression - In: Hüning, H.; Neuhauser, S.; Raus, M.; Ritschel, W. (eds.): Proceedings of Int. Workshop on Neural Networks, RWTH Aachen, Augustinus, 1993, S. 87-95.

Schmidhuber, J. H.; Prelinger, D.: Discovering Predictable Classifications - In: Neural Computation, Volume 5, Number 4, 1993, S. 625-635.

Schröder, H.; Beresford-Smith, B.; Kunde, M.; Turner, G.: Safe and optimal odd-even balancing on the ring task system. - In: Proceedings of the 16th Australian Computer Science Conference (ACSC 16), Brisbane, 3.-5. Feb. 1993, S. 311--319.

Schulz-Zander, R.; Brauer, W. et al: GI-Empfehlungen für das Fach Informatik in der Sekundarstufe II allgemeinbildender Schulen. LOG IN Bd. 13, Heft 3, 1993.

Waschulzik, T.; Quandt, K.; Lewis, M.; Hörmann, A.; Engelbrecht, R; Brauer, W.: Evaluation of an epidemiological data set as an example of the application of neural networks to the analysis of large medical data sets. - In: Artificial Intelligence in Medicine, Proceedings of the 4th Conference on Artificial Intelligence in Medicine Europe, AIME`93, 3.-6.10.1993, München, IOS Press, Amsterdam, 1993, S. 466--476.

Weiß, G.: Action selection and learning in multi-agent environments. - In: Wilson, S. W. et al. (eds.): From animals to animats 2 - Proceedings of the 2nd Int. Conference on Simulation of Adaptive Behavior, Honolulu, Dez. 7--11, 1992. Cambridge: MIT Press, 1993, S. 502--510.

Weiß, G.: Collective learning of action sequences. - In: Proceedings of the 13th Int. Conference on Distributed Computing Systems, Pittsburgh, Mai 25-28, 1993. Los Alamitos: IEEE Computer Society Press, 1993, S. 203--209.

Weiß, G.: Learning to coordinate actions in multi-agent systems. - In: Bajcsy, R. (ed.): Proceedings of the 13th Int. Joint Conference on Artificial Intelligence. Aug. 28 - Sept. 3, 1993. San Mateo: Morgan Kaufmann, 1993, S. 311-316.

Weiß, G.: Lernen und Aktionskoordinierung in Mehragentensystemen. - In: Müller, J. (ed.): Verteilte Künstliche Intelligenz - Methoden und Anwendungen. Mannheim: BI Verlag, 1993, S. 122--132.






Vorträge

Brauer:
19.2.93 Ergebnistransfer wissenschaftlicher (Grundlagen-) Forschung in der KI
Podiumsdiskussion, 2. Deutsche Tagung ''Expertensysteme`` 17.-19.2.1993 in Hamburg
27.2.93 KI auf dem Weg in die Normalität
11. Frühjahrstagung für Künstliche Intelligenz (KIFS'93) des FBIder GI, Günne am Möhnesee
21.7.-24.7.93 Concurrent Processes and Petri Nets
4 Vorträge bei der International Summer School on Proof and Computation, Marktoberdorf 1993
18.10.93Laudatio auf Carl Adam Petri - Verleihung der Zuse-Medallie der GI. Eröffnung des 1. Europäischen Informatik-Kongresses, SYSTEMS '93, München
19.11.93Verteilte Systeme, nebenläufige Prozesse - Aufbau, Analyse, Beschreibung
Festkolloquium, Fachbereich Mathematik und Informatik, Freie Universität Berlin

Desel:
Juni 93 Shortest path of reachability graphs
XIV. Int. Conference on Applications and Theory of Petri Nets, Chicago
Juni 93 Regular marked Petri Nets
Graph-Theoretical Concepts in Computer Science,
Arnheim
Februar 93 Bausteine eines kompositionalen Beweiskalküls für netzmodellierte Systeme
Universität Hamburg
September 93 Two results on Petri Nets and linear algebra
CALIBAN Annual General Meeting, Fischbachau

Eldracher:
13.7.93 Neural Subgoal Generation Using Back-Propagation
World Conference on Neural Networks, Portland Oregon

Hernández:
18.6.93 Reasoning with qualitative representations: Exploiting the structure of space
QUARDET'93, Barcelona, Spanien
2.7.93 Qualitative Repräsentation räumlichen Wissens
Kolloquium ``Sprach- und Bildverarbeitung'' der Universität Bielefeld
20.8.93 Using the intrinsic structure of relational domains to improve constraint propagation and relaxation procedures
NATO Advanced Study Institute on Constraint
Programming, Pärnu, Estland
13.9.93 Hybride und integrierte Ansätze zur Raumrepräsentation und ihre Anwendung
Workshop-Einführungsvortrag im Rahmen der 17. Fachtagung für Künstliche Intelligenz an der Humboldt-Universität zu Berlin.
18.9.93 Position Paper
Workshop on Spatial Relations, Marciana Marina, Italien
20.9.93 Maintaining qualitative spatial knowledge
COSIT'93. Marciana Marina, Elba Island, Italien

Holzer:
16.3.93 Das Nichtleerheitsproblem für reguläre Sprachen
19. Workshop über Komplexitätstheorie und effiziente Algorithmen, Jena
22.6.93 Die Komplexität iterierten Einfügens
20. Workshop über Komplexitätstheorie, effiziente Algorithmen und Datenstrukturen, Berlin
22.6.93 0=Tally-AFA ist PSPACE-vollständig
20. Workshop über Komplexitätstheorie, effiziente Algorithmen und Datenstrukturen, Berlin
12.-15.7.93 The very low complexity of deterministic 0L languages: D0L is in AC0
Conference on Developments in Language Theory, Turku-Finnland
23.-27.8.93 On the complexities of linear LL(1) and LR(1) grammars
9th Int. Conference on Fundamentals of
Computation Theory, Szeged, Ungarn
7.-10.10.93 Das Nichtleerheitsproblem für alternierende endliche Automaten
3. Theorietag ``Automaten und Formale Sprachen'', Dagstuhl

Kiehn:
1.9.93 Proof systems for cause based equivalences.
MFCS 93, Danzig, Polen.
7.12.93 Über Lokalität und Kausalität in Prozealgebren.
Kolloquiumsvortrag, Universität Hildesheim.

Kindler:
2.7.93 Eigenschaften verteilter Systeme,
Workshop SFB 342 TP A3/A6
27.9.93 A scott domain of distributed runs,
ESPRIT Project Caliban, Annual General Meeting, Fischbachau
16.12.93Verteilte Abläufe verteilter System,
Informatik-Tag der Humboldt-Universität zu Berlin

Kunde:
9.6.93 Datentransportalgorithmen auf Gittern
Kolloquium, Universität Passau
13.9.93 The all-to-all mapping and its impact on routing and sorting on grids
Workshop Parallele und verteilte Algorithmen, Dagstuhl
29.10.93Schnelle Sortiermethoden für Prozessornetzwerke
Kolloquium, Universität Karlsruhe (TH)
17.12.93Sortieren und Pakettransport auf Pro-zessor-netz-werk-en,
Kolloquium, Universität Stuttgart

Lange:
8.1.93 Parallelism and Formal Languages
Boston University, USA
15.1.93 Parallelism and Formal Languages
McGill Univ., Montreal
21.5.93 Complexity and Structure in Formal Language Theory
FCRC 93, San Diego, USA
17.9.93 Problems of Parallel Complexity Theory
Dagstuhl-Seminar
29.9.93 Lindenmayersysteme und Komplexität
TU Magdeburg
30.9.93 Schnelle Algorithmen für D0L-Sprachen
TU Magdeburg
26.11.93 Formal Languages in the view of Structural Complexity Theory
Univ. Paris 7, Frankreich

Niedermeier:
16.11.93Datenunabhängigkeit bei Parallelen Registermaschinen
21. Workshop über Komplexitätstheorie und effiziente Algorithmen, Darmstadt
15.12.93Data-Independences of Parallel Random Access Machines
13th FST&TCS, Bombay, Indien

Reisig:
28.1.93 Proving Distributed Algorithms Correct
University Milano, Italien
18.2.93 The Synthesis Problem of Petri Nets
STACS Würzburg
5.3.93 Proving Distributed Algorithms Correct
Technical University Athen, Griechenland
22.3.93 Proving Distributed Algorithms Correct
University Moscow, Ruland
April 93Spezifikation, Modellierung und Korrektheit verteilter Algorithmen
PASA-Workshop, Bonn
7.5.93 Concurrent Temporal Logic
University Lissabon, Portugal
4.6.93 Specification, Modelling and Verification of Concurrent Discrete Event Systems
Imperial College London, Großbritannien
September 93 Formal Methods for Concurrent Systems Design: A Survey
Working Conference on Massively Parallel Programming Models, Berlin
September 93 Spezifikation, Modellierung und Korrektheit von Informationssystemen
GI-Fachtagung: Petri-Netze im Einsatz für den Entwurf von Informationssytemen, Berlin
16.12.93Verteiltes Rechnen: Im wesentlichen das Herkömmliche oder etwas grundlegend Neues?
Antrittsvorlesung, Humboldt-Universität zu Berlin

Rossmanith:
26.2.93 Extended Locally Definable Acceptance Types
STACS'93, Würzburg
16.11.93Faster sorting and routing on grids with diagonals
21. Workshop über Komplexitätstheorie, effiziente Algorithmen und Datenstrukturen, Darmstadt
16.12.93On the power of reading and writing simultaneously in parallel computations
ISAAC'93, Hong Kong

Schmidhuber:
März 93 Adaptive redundancy reduction
King's College, London, Großbritannien
März 93 Adaptive redundancy reduction
Cambridge University, Cambridge, Großbritannien
März 93 A novel unsupervised classification method.
Vortrag für ANN 1993, Brighton, Großbritannien
Juli 93 Redundanzreduktion durch neuronale Netzwerke
Vortrag an der Technischen Universität Berlin
August 93 Zur Haltewahrscheinlichkeit von Turingmaschinen
Habilitationsvortrag für TU München
September 93 A self-referential weight matrix
Vortrag für ICANN 1993, Amsterdam, Holland
Oktober 93 Redundanzreduktion durch neuronale Netzwerke
Vortrag am DFKI in Kaiserslautern
Oktober 93 ``Neural'' redundancy reduction
Vortrag für PASE 1993, Ascona, Schweiz
November 93 Reinforcement directed information acquisition in Markov environments
Vortrag für NIPS workshops 1993, Vail, Colorado, USA
November 93 Adaptive redundancy reduction
Vortrag an der University of Colorado, Boulder, Colorado, USA

Weiß:
10.3.93 Multi-agent reinforcement learning
NATO ASI ``The Biology and Technology of Intelligent Autonomous Systems'', 1.-12.3.1993, Ivano, Italien
29.4.93 Lernen und Aktionskoordinierung in Mehr-agen-ten-sys-te-men
Gründungsworkshop der Fachgruppe Verteilte Künstliche Intelligenz der Gesellschaft für Informatik, 29.-30.4.1993, Saarbrücken
1.9.93 Learning to coordinate actions in multi-agent systems.
13th Int. Conference on Artificial Intelligence, 28.8.-3.9.1993, Chambery, Frankreich






Vorlesungen und Seminare

Barnard, Kiehn, Mader, Reisig:
Hauptseminar: Calculus of Communicating Systems, WS 92/93

Barnard, Brauer, Kiehn, Mader:
Hauptseminar: Der Modale µ-Kalkül, SS 93

Brauer:
Vorlesung: Theorie formaler Sprachen und Automaten II, SS 93, 2SWS
Vorlesung: Neuronale Netze, SS 93, 2SWS
Vorlesung: Theorie paralleler Prozesse, WS 93/94, 2SWS
Vorlesung: Theorie kommunizierender Prozesse, WS 93/94, 2SWS

Brauer, Gomm, Heise, Kiehn, Mader:
Hauptseminar: Formale Methoden in der Künstlichen Intelligenz,
Hauptseminar: WS 93/94

Brauer, Eldracher, Weiß:
Praktikum: Methoden der Künstlichen Intelligenz: Konnektionismus,
Praktikum: SS 93

Brauer, Hernández:
Praktikum: Methoden der KI zum Thema: Eine Einführung in die
Praktikum: Programmiersprache LISP, WS 93/94

Brauer, Hahndel, Hernández, Struß, Weiß:
Hauptseminar: Verteilte Künstliche Intelligenz, WS 93/94

Brauer, Schmidhuber, Weiß:
Hauptseminar: Lernverfahren für Neuronale Netze

Kunde:
Vorlesung: Parallele Algorithmen II, SS 93 (Universität Passau), 3SWS
Vorlesung: Informatik für Nichtinformatiker II, SS 93
Vorlesung: (Universität Passau), 2SWS
Vorlesung: Parallele Algorithmen, WS 93/94
Vorlesung: (Universität München), 3SWS
Übungen zur Vorlesung Informatik für Nichtinformatiker II
Übungen (mit H. Röder), SS 93 (Universität Passau), 3SWS
Übungen zur Vorlesung Parallele Algorithmen (mit V. Heun), WS 93/94

Lange, Holzer, Niedermeier, Rossmanith:
Hauptseminar: Eine Einführung in parallele Algorithmen, SS 93

Lange:
Vorlesung: Kryptologie und Komplexität, SS 93, 2SWS
Vorlesung: Algorithmische Geometrie, SS93, 2SWS
Vorlesung: Theorie formaler Sprachen und Automaten, WS92/93, 3SWS
Vorlesung: Berechenbarkeit und Entscheidbarkeit, WS 93/94, 3SWS
Vorlesung: Strukturelle Komplexitätstheorie, WS 93/94, 2SWS

Rossmanith:
Vorlesung: Formal Languages and Automata Theory, WS 93,
Vorlesung: (Am Masaryk Institute for Advanced Sciences, TU Prag)

Schmidhuber:
Seminar: Lernende Neuronale Netze, SS 93
Vorlesung: Lernalgorithmen für Neuronale Netze, WS 93/94, 2SWS






Sonstige Tätigkeiten

Brauer:

Barnard:

Eldracher:

Desel:

Gold:

Gomm:

Heise:

Hernández:

Kiehn:

Kinder:

Kindler:

Kunde:

Lange:

Reisig:

Rossmanith:

Schmidhuber:

Weiß:






Diplomarbeiten und Fortgeschrittenenpraktika

Alle Arbeiten wurden 1993 abgeschlossen.

Brauer:
Diplomarbeiten in Zusammenarbeit mit T. Waschulzik (GSF, Medis-Institut):

  1. Segmentation von Computertomogrammen mit Hilfe neuronaler Netze
    Bearbeiter: R. Däschlein
  2. Impulssynchronisation in mehrschichtigen neuronalen Netzen
    Bearbeiterin: U. Kraut
  3. Segmentierungsverfahren zur Präklassifikation visuell erfaßter Muster
    Bearbeiter: O. Spickhoff
  4. Untersuchungen eines strukturadaptiven Algorithmus zum Aufbau von RBF-Netzen mit topologisch codierter Ausgabeschicht
    Bearbeiter: M. Ehrlicher
  5. Erstellen eines halbautomatischen Systems zur Analyse großer Datenmengen mit neuronalen Netzen
    Bearbeiterin: F. Grothe

Diplomarbeiten in Zusammenarbeit mit D. Butz und K. Eder (Kratzer Automatisierung):

  1. Qualitative und quantitative Untersuchungen zur Darstellung von statischen Funktionen in neuronalen Netzen, die als Assoziativspeicher dienen
    Bearbeiter: Klaus Noack
  2. Lernverhalten ausgewählter neuronaler Netze für die Spracherkennung
    Bearbeiter: Harold-Clement Mayer
  3. Untersuchungen zur rückgekoppelten Hypothesenbildung in Single-Spike-Netzen
    Bearbeiter: Michael Sturm

Diplomarbeit in Zusammenarbeit mit Dr. W. Finnoff (Siemens ZFE):

  1. Estimation of Probability Densities Using Neural Networks
    Bearbeiter: Dirk Ormoneit

Diplomarbeit in Zusammenarbeit mit Dr. W. X. Schneider (Max-Plank-Institut für psychologische Forschung):

  1. Anwendung von oszillierenden Netzwerken auf das Problem der Segmentierung in der Wahrnehmung
    Bearbeiter: Josef Wackerl
Diplomarbeiten in Zusammenarbeit mit Dr. K. Schill (Institut für Medizinische Psychologie, Ludwig-Maximilians-Universität München)
  1. Entwicklung eines interaktiven wissensbasierten Systems zur Untersuchung des zeitlichen Schlußfolgerns
    Bearbeiter: Oliver Gebhard
  2. Übertragung von Strategien bei der Koordination von Prozessen auf Aufmerksamkeitskonzepte
    Bearbeiterin: Angelika Mayer

Eldracher:
Diplomarbeiten:

  1. Kohonens selbstorganisierende Merkmalskarten zum Stabbalancieren
    Bearbeiter: Markus Rathmayer (- in Zusammenarbeit mit Peter Braun, Lehrstuhl Prof. Dr. Bode)
  2. Bahnplanung für Roboter, Erzeugung von Subzielen mit künstlichen Neuronalen Netzen
    Bearbeiter: Boris Baginski
  3. Inverse Modellierung der Kinematik von Robotern mit wachsenden Zellstrukturen
    Bearbeiter: Harald Dechentreiter
Fortgeschrittenenpraktika:
  1. Neuronale Generierung von Subzielen für Roboter
    Bearbeiter: Boris Baginski
  2. Optimal Brain Surgeon - Prunen in Feed Forward Netzen
    Bearbeiter: Christian Schittenkopf
  3. Trajektorienplanung mit Wegespeicher
    Bearbeiter: Alexander Staller
  4. Chunking-Systeme als Trajektorienspeicher
    Bearbeiter: Axel Huber
  5. Erlernung von Roboter-Bewegungstrajektorien in Umgebungen mit Hindernissen
    Bearbeiter: Fritz Birnbacher
  6. Erlernung von Roboter-Bewegungstrajektorien in Umgebungen mit Hindernissen
    Bearbeiter: Reinhard Eisele

Gomm:
Diplomarbeiten:

  1. Temporale Modellierung und Korrektheit: Entwurf eines verteilten Lifts
    Bearbeiter: Thomas Hahn
  2. Formale Spezifikation, Modellierung und Verifikation eines verteilten Eisenbahnsystems
    Bearbeiter: Andreas Holz
  3. Algebraische Verifikationsmethoden für Unerreichbarkeit in Petrinetzen
    Bearbeiter: Micaela-Daphne Radola

Hernández:
Diplomarbeiten:

  1. Ein Modell zur qualitativen Beschreibung von Grundformen
    Bearbeiter: Stefan Högg
  2. Qualitative Beschreibung zusammengesetzter Formen
    Bearbeiterin: Irmgard Schwarzer

Holzer:
Fortgeschrittenenpraktikum:

  1. Ein Parser für lineare Grammatiken
    Bearbeiter: Barbara König, Krinke Snurawa

Kinder:
Diplomarbeiten:

  1. Trajektoriengenerierung durch Trajektorienspeicherung mittels adaptiver, neuronaler Raumrepräsentation. Januar 1994.
    Bearbeiter: Till Brychcy
  2. Anwendung von Optimierungsverfahren auf das Training von Neuronalen Netzen.
    Bearbeiter: Jens Sundermann (- in Zusammenarbeit mit Dr. Günter Gramlich, DLR Oberpfaffenhofen)
  3. Klassifikation von Montagezuständen eines Roboters zur Aktivierung von Regelungsphasen mit Hilfe Neuronaler Netze
    Bearbeiter: Oliver Beran

Lange:
Diplomarbeit:

  1. Generierung von fast optimalen 2D-Triangulationen
    Bearbeiter: Alexander Sacher

Fortgeschrittenenpraktikum:

  1. Pointerjumping auf dem Hypercube
    Bearbeiter: Christian Wendl

Niedermeier:
Diplomarbeit:

  1. Implementierung eines parallelen Registermaschinentyps auf Rechnern mit verteiltem Speicher.
    Bearbeiter: Thomas Ampferl

Fortgeschrittenenpraktikum:

  1. Implementierung einfacher paralleler Algorithmen mit verschiedener Datenpartitionierung
    Bearbeiter: Thomas Ampferl
  2. Implementierung einfacher paralleler Algorithmen mit verschiedener Datenpartitionierung
    Bearbeiter: Sascha Groh

Rossmanith:
Diplomarbeit:

  1. Entwicklung eines Programmiersystems für kommunikationsintensive Algorithmen auf massiv parallelen Rechnern mit verteiltem Speicher
    Bearbeiter: Sascha Groh

Fortgeschrittenenpraktika:

  1. Algorithmen mit verschiedener Datenpartitionierung
    Bearbeiter: Thomas Ampferl, Sascha Groh
  2. Mikroökonomische Lastbalancierung
    Bearbeiter: Christian Sucrow

Weiß:
Diplomarbeit:

  1. Examinations on the algebra of genetic algorithms
    Bearbeiter: Reimar Hofmann ( - in Zusammenarbeit mit G. Norman, University of Edinburgh)

Fortgeschrittenenpraktika:

  1. Maschinelles Lernen und Gruppenbildung in einfachen Mehragentensystemen
    Bearbeiter: Peter Turck
  2. Erweiterungen des Standard-Klassifizierungssystems
    Bearbeiter: Armin Wirth





Promotionen

Externe Promotion:
Jürgen Hollatz, Siemens ZFE
Integration von regelbasiertem Wissen in neuronalen Netzen
Betreuer: W. Brauer






Forschungsberichte

Die Forschungsberichte Künstliche Intelligenz enthalten vornehmlich Vorabveröffentlichungen, spezialisierte Einzelergebnisse und ergänzende Materialien, die in der KI/Kognitionsgruppe am Lehrstuhl Prof. Brauer und in der KI-Gruppe Intellektik am Lehrstuhl Prof. Jessen entstanden sind. Eine Zusammenstellung aller derzeit lieferbaren FKI-Berichte und einzelne Exemplare aus dieser Reihe können bei folgender Anschrift angefordert werden:

FKI
Institut für Informatik
Lehrstuhl Prof. Dr. W. Brauer, H2
TECHNISCHE UNIVERSITÄT MÜNCHEN
D-80290 München

Tel.: +49-89-2805217
Telex: tumue d 05 - 22854
Fax: +49-89-2105-8207, +49-89-2105-8483
E-Mail: fki@informatik.tu-muenchen.de

Die aktuelle FKI-Liste, einige Kurzfassungen zu den Berichten sowie ganze Berichte (komprimierte Postscript-Dateien) können zudem auf elektronischem Wege bezogen werden:

  1. ftp:
    Login: anonymous
    Maschine: flop.informatik.tu-muenchen.de (131.159.8.35)
    Verzeichnis: pub/fki
  2. gopher:
    Server: gopher.informatik.tu-muenchen.de
    Anzuwählende Menüpunkte:
    Informationsangebot der einzelnen Lehrstühle
    VII Theoretische Informatik, Grundlagen der KI
  3. World Wide Web
    http://papa.informatik.tu-muenchen.de/fkiberichte/






Rufnummern und E-mail-Adressen

Name Tel. E-mail Adresse
Barnard, D. 2105-8474 barnard@informatik.tu-muenchen.de
Brauer, W. 2105-2401 brauer@informatik.tu-muenchen.de
Eldracher, M. 2105-2407 eldrache@informatik.tu-muenchen.de
Gold, R. 2105-2387 gold@informatik.tu-muenchen.de
Gomm, D. 2105-8237 gomm@informatik.tu-muenchen.de
Heise, A. 2105-2395 heise@informatik.tu-muenchen.de
Hern´andez, D. 2105-2606 danher@informatik.tu-muenchen.de
Holzer, M. 2105-2395 holzer@informatik.tu-muenchen.de
Kiehn, A. 2105-2388 kiehn@informatik.tu-muenchen.de
Kinder, M. 2105-8476 kinder@informatik.tu-muenchen.de
Kindler, E. 2105-8474 kindler@informatik.tu-muenchen.de
Kunde, M. 2105-2390 kunde@informatik.tu-muenchen.de
Lange, K.-J. 2105-2403 lange@informatik.tu-muenchen.de
Mader, A. 2105-8238 mader@informatik.tu-muenchen.de
Niedermeier, R. 2105-2397 niedermr@informatik.tu-muenchen.de
Rossmanith, P. 2105-2397 rossmani@informatik.tu-muenchen.de
Schmidhuber, J. 2105-2406 schmidhu@informatik.tu-muenchen.de
Schoett, O. schoett@informatik-tu-muenchen.de
Weiß, G. 2105-2407 weissg@informatik.tu-muenchen.de



Martin Eldracher, eldrache@informatik.tu-muenchen.de, 1996-01-11