Tätigkeitsbericht 1990

Arbeitsbereich Prof. Dr. Wilfried Brauer

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

Institut für Informatik
Technische Universität München
Arcisstr. 21
D-8000 München 2




0 Inhaltsverzeichnis

  1. Mitglieder
    1. Professoren
    2. Wissenschaftliche Mitarbeiter
    3. Sekretärinnen
    4. Studentische Hilfskräfte
    5. Gäste
    6. Drittmittel
  2. Darstellung der Forschungsvorhaben
    1. Projekte
    2. Weitere Forschungsvorhaben
  3. Veröffentlichungen
  4. Vorträge
  5. Vorlesungen und Seminare
  6. Sonstige Tätigkeiten

1 Mitglieder

1.1 Professoren

o. Prof. Dr. Wilfried Brauer
Prof. Dr. Klaus-Jörn Lange
Prof. Dr. Wolfgang Reisig


1.2 Wissenschaftliche Mitarbeiter

Dr.habil. Volker Diekert (Privatdozent, beurlaubt bis 31.3.90, Vertretungsprofessur in Stuttgart)
Christian Freksa, Ph.D. (Akad. Rat a.Z., beurlaubt bis 30.4.90, Forschungsaufenthalt in Berkeley)
Dr. Birgit Jenner (wiss. Mitarbeiterin, seit 1.8.90)
Dr. Manfred Kunde (wiss. Mitarbeiter)
Oliver Schoett, Ph. D. (Akad. Rat a.Z.)
Dr. Walter Vogler (Akad. Rat a.Z.)
Petra Bräunling (wiss. Mitarbeiterin, bis 31.5.90)
Jörg Desel (wiss. Mitarbeiter)
Rob von Glabbeek (wiss. Mitarbeiter, bis 31.7.90)
Robert Gold (wiss. Mitarbeiter)
Dominik Gomm (wiss. Mitarbeiter)
Andreas Heise (wiss. Mitarbeiter)
Daniel Hernández (wiss. Mitarbeiter)
Ekkart Kindler (wiss. Mitarbeiter, seit 16.11.90)
Erwin Klöck (wiss. Mitarbeiter bis 31.10.90)
Inga Niepel (wiss. Mitarbeiterin bis 31.12.90)
Klaus Reinhardt (wiss. Mitarbeiter, 1.5.90-31.7.90)
Peter Rossmanith (wiss. Mitarbeiter, seit 1.11.90)
Bernhard Schätz (wiss. Mitarbeiter seit 1.3.90)
Thomas Tensi (wiss. Mitarbeiter)
Rolf Walter (wiss. Mitarbeiter)
José Manuel Benedetti (DAAD Stipendiat bis Juli 90)
Marco Dorigo (Gastwissenschaftler)
Jürgen Schmidhuber (Siemens-Stipendiat)
Gerhard Weiß (TU-Stipendiat)


1.3 Sekretärinnen

Ingeborg Biberger
Paula Grylka
Sabine Karl (bis 28.2.90)


1.4 Studentische Hilfskräfte

Anton Beschta Hard- und Software-Betreuung (insbes. Unix, e-mail)
Harald Hadwiger Unterstützung bei Forschung und Lehre
M. Heckner Unterstützung bei Forschung und Lehre
Paul Jetschny Hard- und Software-Betreuung
Ekkart Kindler Unterstützung bei Forschung und Lehre (bis 15.11.90)
Angela Marquardt Literaturbeschaffung und -verwaltung, Textverarbeitung, Büro-organisation
Sabine Mühlbauer Pflege, Beratung und Vorführung von Petrinetzwerkzeugen
Rolf Niedermeier Unterstützung bei Forschung und Lehre
Gerd Pauli Hard- und Software-Betreuung
G. Riedle Unterstützung bei Forschung und Lehre
Thomas Röll Hard- und Software-Betreuung (insbes. Unix, e-mail)
Dieter Stein Unterstützung bei Forschung und Lehre
Kai Zimmermann Software-Entwicklung


1.5 Gäste

14.2.90 Lore Petrucci (Université Paris-Sud)

23.5.90 Javier Esparza (Universität Hildesheim)
The Rank Theorem of Free-Coice Nets and its Consequences

6.7.90 Stefan Wermter (Universität Dortmund)
Analyse von Nominalphrasen mit symbolischen/subsymbolischen Methoden

19.3.-23.3.90 Torben Hagerup (Universität Saarbrücken)
Improved Deterministic Parallel Integer Sorting

15.5.90 Josef Traub (Computer Science Department, Columbia University)
Power and Limitations of Randomization

4.6.-13.6.90 P. Starke (Humboldt-Universität zu Berlin)

18.6.-21.6.90 Birgit Jenner (Universität Barcelona)
A sequential characterization of circuit classes

18.6.-21.6.90 C. Alvarez (Universität Barcelona)
Logarithmic Space Counting Classes

21.6.90 Karel Culik II (Department of Computer Science, University of South Carolina)
Fractal Geometry and Automata-theoretic Methods for Image Synthesis

3.7.90 Dirk Taubner (Siemens AG, ZFE IS INF2)
Maschinell unterstützte Verifikation paralleler Prozesse

4.7.-6.7.90 Edward Ochmanski (Polnische Akademie der Wissenschaften,Warschau)
On Confluent Semi-Commutation

12.7.90 Ron Book (University of Califonia at Santa Barbara)
Confluent Thue Systems - an Introduction to Rewriting Systems

24.7.90 M. Sonnenschein (RWTH Aachen)
Ein objektorientiertes und datengesteuertes Programmierkonzept für Multicomputer auf der Grundlage dynamischer Petrinetze

26.7.90 Andreas Brandstädt (Heinrich-Heine-Universität Jena)
Über algorithmische Graphentheorie und Informatik

31.7.-3.8. 90 V. Vinay (Indian Institute of Science, Bangalore)
Circuit Characterizations of Nondeterministic Classes

13.8.-17.8.90 P. Starke (Humboldt-Universität zu Berlin)

17.9.-21.9.90 A. Goerdt (Universität Duisburg)
Zur Leistungsfaehigkeit von Resolutionsrestriktionen

22.9.-6.10.90 J. Dassow (Technische Universität Magdeburg)
Kettencode-Bildsprachen und geometrische/graphentheoretische Eigenschaften

26.9.90 B. A. Trakhtenbrot (Tel Aviv University)
Some Laws and Anomalics in the Semantics of Nets

5.11.-7.11.90 C. Damm (Humboldt-Universität zu Berlin)
Vollständige Probleme für log-space-Zählklassen und ihre parallele Komplexitaet

5.11.-7.11.90 M. Krause (Humboldt-Universität zu Berlin)
Kommunikations-Schaltkreis-Schemata und Zaehlklassenseparierung für nichtdeterministische Branching Programme

26.11.-30.11. G. Buntrock (Universität Würzburg)
Akzeptanztypen und logarithmischer PLatz

26.11.90 Christoph Schlieder (Universität Hamburg)
Anordnungswissen: Grundlagen und Anwendung

29.11.90 Nguyen Cat Ho,. Hanoi
Hedge-Algebren

29.11.90 Petra Leuchtenberg
Informationsverarbeitung im Riechhirn der Ratte

1.6 Drittmittel

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

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

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

DFG-Projekt "Unäre Sprachen im unteren Komplexitätsbereich" (La 618/1-1)

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-2)

DFG-Projekt: "PAKI - Parallelverarbeitungsmodelle in der Künstlichen Intelligenz" (Br 609/4-2)

DFG-Reisebeihilfe: Untersuchungen zur Rolle von Unschärfe im Beschreibungssprachen aus repräsentationtheoretischer Sicht (Fr 806/1-1)

Kooperation mit dem ZFE F2 der Siemens AG auf den Gebieten Künstliche Intelligenz /Konnektionismus und Software-Technik sowie Algorithmen und Architekturkonzepte für Prozessorfelder

ESPRIT BRA Project No 3148 DEMON: "Design Methods Based on Nets".

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






2 Darstellung der Forschungsvorhaben

2.1 Projekte

Brauer, Desel, Gold, Gomm, Heise, Kindler, Reisig, Walter

SFB 342, Teilprojekt A3 SEMAFOR

In diesem Projekt werden theoretische Grundlagen und formale Hilfsmittel für die Spezifikation, den Entwurf und die Analyse nicht-sequentieller Systeme weiterentwickelt und für die Praxis aufbereitet. Dabei wird von verschiedenen Ansätzen, insbesondere Petrinetzen, abstrakten und konkreten Programmiersprachen, temporaler Logik und Statecharts ausgegangen und ein integriertes Entwurfskonzept angestrebt.
Im Jahr 1990 wurden Arbeiten zu begrifflich-konzeptionellen Grundlagen nicht-sequentieller Systeme und zur Beschreibung in solchen Systemen (unter Beachtung der Kausalität) publiziert. Die Integration von temporaler Logik mit Petrinetzen wurde durch Konzepte und Operatoren von UNITY vorangebracht. Für die dazu "passende" Netzklasse, mit Term-spezifizierten Datenstrukturen, wurden Analyseverfahren entwickelt. Die bei diesen Arbeiten entwickelten Techniken werden in vorhandene Petrinetz-Werkzeuge integriert.Erste Fallstudien, teilweise in Kooperation mit anderen Teilprojekten des Sonderforschungsbereiches und der SIEMENS AG, wurden begonnen.



Heise, Reisig

SFB 342, Kooperationsprojekt mit der Humboldt-Universität zu Berlin

Die von Prof. Starke an der Humboldt-Universität erstellte Software zur Analyse von Petrinetzen wird um weitere Komponenten ergänzt, insbesondere solche zum symbolischen Umgang mit strukturierten Marken.



Brauer, Vogler, Desel, Diekert, Gold, Gomm, Kindler, Reisig, Walter

ESPRIT-Projekt DEMON

Die Konstruktion reaktiver Systeme ist in drei Phasen zerlegbar: Die Spezifikationsphase, mit i.a. nicht-operationellen Systembeschreibungen, die Entwurfsphase mit Hardware- und Software-unabhängigen operationellen Beschreibungen, und die Implementierungsphase, in der operationelle Beschreibungen auf konkrete Hardware und Software abgebildet werden.
Das Projekt konzentriert sich auf die ersten beiden Phasen und den systematischen Übergang zwischen ihnen. Zu diesem Zweck wurden für verschiedene Systemmodelle (Petrinetze, Ereignisstrukturen, Prozeßalgebren) Äquivalenz-, Verfeinerungs- und Kompositionsbegriffe gebildet, untersucht und in die vorhandene Literatur eingebettet. Tiefliegende Konsequenzen des Prinzips der Trennung von Nichtdeterminismus und Synchronisation (free-choice) wurden aufgedeckt und publiziert. Temporallogische Methoden zum Umgang mit Lebendigkeits-, Sicherheits- und Fairnesseigenschaften in Petrinetzen wurden entwickelt.



Brauer, Freksa, Bräunling, Hernández, Klöck, Beschta, Zimmermann:

PAKI: Parallelverarbeitungsmodelle für Problemstellungen in der Künstlichen Intelligenz

Die Arbeiten an dem Projekt PAKI wurden abgeschlossen.
Ziel des zweiten Abschnitts des Projektes Parallelverarbeitungsmodelle in der KI war die Entwicklung kognitiv plausibler Verarbeitungsmodelle für wissensbasierte, natürlichsprachliche Auskunftssysteme. Dabei konzentrierten sich die Arbeiten auf die folgenden Themengebiete: (i) die psychologischen Grundlagen der Raumwahrnehmung und der Navigation in städtischen Umgebungen; (ii) die Repräsentation räumlicher Gegebenheiten und Formalismen des räumlichen Schließens; (iii) ein interaktives Modell der natürlichsprachlichen Formulierung von Wegbeschreibungen.
Es wurden alternative Repräsentationsformalismen zu den etablierten Darstellungen von Raum in einem kartesischen Koordinatensystem gesucht, da dieses eine Genauigkeit und Spezifizität der Repräsentation erfordert, die kognitiv nicht plausible erscheint. Die kognitiven Kategorien der Richtung und Entfernung werden dabei als Grundkategorien betrachtet. Ein weiterer Schwerpunkt lag auf der Entwicklung von Kalkülen des räumlichen Schließens, wobei eine Erweiterung des Allenschen Zeitkalküls versucht wurde.
Die sprachliche Beschreibung räumlicher Gegebenheiten, insbesondere die Gesetzmäßigkeiten der Bezeichnung von Objekten in kontextuell situierten Äußerungen bildete einen weiteren Schwerpunkt der Arbeiten. Hier wurden die Abhängigkeiten und Interdependenzen von sprachlicher Beschreibung und Situationskontext untersucht und gefolgert, daß für eine adäquate Objektbenennung als Repräsentationskomponenten Relationsschemata und Objektschemata zusätzlich zum Lexikon angenommen werden müssen.
Ein Modell der Sprachproduktion wurde entwickelt, wobei insbesondere für das Problem der Unterscheidung von alternativen Formulierungen bzw. Paraphrasen berücksichtigt wurde. Unter diesem Blickwinkel wurde besonders das Zusammenspiel zwischen semantischer Repräsentation und dem Formulierungsprozeß thematisiert und ein Mechanismus postuliert, der in mehreren Interaktionen zwischen beiden Ebenen eine Verfeinerung der Äußerung auf beiden Ebenen bewirkt.



Brauer, Freksa, Hernández, Marquardt, Merz, Schätz, Schill (Med. Psychologie, LMU), Zimmermann

Relationale Modelle zur kontextabhängigen Wissensrepräsentation

Hauptziel dieses Projekts ist es, relationale Modelle zur Repräsentation kontextabhängigen - insbesondere räumlichen Wissens, wie es zur natürlichsprachlichen Objektbeschreibung verwendet wird, zu untersuchen. Unter einem relationalen Modell verstehen wir die Darstellung räumlicher Gegebenheiten und anderer objektspezifizierender Merkmale mit Hilfe von relativen Dimensionsangaben. Diese Darstellungen sind "unterbestimmt", d.h. sie können mehreren tatsächlichen Situationen entsprechen. Sie können dennoch zur Generierung adäquater Beschreibungen verwendet werden, da diese stets innerhalb eines bestimmten Kontextes zu interpretieren sind. Zur Handhabung der entstehenden Relationennetze werden verschiedene constraint satisfaction und reasoning maintenance-Algorithmen untersucht.
Ein Repräsentations- und Inferenzschema für zeitliche Relationen auf der Grundlage 'Konzeptueller Nachbarschaften' von Relationen wurde entwickelt. Dieser Ansatz soll auf räumliche Relationen übertragen werden.



Brauer, Dommel, Freksa, Hernández, Hoffman (MPI Psychologische Forschung, München) Hollack, Huber, Hutter, Krachenfels, Laußermair, Schätz, Schmidhuber, Thomas, Weiß

Konnektionistische Modelle, neuronale Netze und genetische Algorithmen

Dieses Projekt beschaeftigt sich mit folgenden Themenkomplexen:
1. Neuronale Netze und Zeit: Es sollen Verfahren zur adaptiven zeitlichen Dekomposition von Ereignis- und Aktionssequenzen in dynamischen Umgebungen mittels neuronaler Netze entwickelt werden. Ein Schwerpunkt hierbei ist die `adaptive Subzielgenerierung'. Ziel ist es, neuronale Netze lernen zu lassen, `wie man teilt und herrscht'. Eine beabsichtigte Anwendung ist die adaptive Steuerung von zielgerichteten Roboterbewegungssequenzen.
2. Genetische Algorithmen: Untersuchung der Frage, inwieweit auf dem Prinzip der biologischen tauglich sind.



Brauer, Taubner (Siemens ZFE), Filkorn (Siemens Promotions-Stipendiat)

Methoden und Techniken zur Verifikation

Basierend auf automatentheoretischen Methoden werden Methoden und computergestützte Techniken zur symbolischen Verifikation synchroner sequentieller Schaltungen sowie zur Verifikation von mit Mitteln der Prozeßalgebren beschriebenen parallelen Prozeßspezifikationen entwickelt.



Brauer, Geiger, Waschulzik (Kratzer Automatisierung, Unterschleißheim), Arnoldi, Diekl, Eder, Eldracher, Kinder, Menke-Glückert, Scheppler (Lehrstuhl für Integrierte Schaltungen, TUM)

Konzepte, Hilfsmittel und Anwendungen für konnektionistische Systeme

Weiterentwicklung der Netzwerkbeschreibungssprache um neue biologisch motivierte Neuronenmodelle, Repräsentation mehrdimensionaler funktionaler Abhängigkeit und Verfahren der Informationskodierung und -verarbeitung in neuronalen Netzen, Erkennung natürlich-sprachlicher Sätze und Klassifikation großer Datenmengen mit neuronalen Netzen.



Diekert, Heise

ESPRIT-BRA Arbeitsgruppe ASMICS

Untersuchungen in algebraischen und syntaktischen Methoden der Informatik, insbesondere mit Hilfe der Spurtheorie von Mazurkiewicz und der Theorie algebraischer Netzschemata



Kunde, Tensi

Entwurf und Analyse von grundlegenden Algorithmen für Prozessornetzwerke (unterstützt durch DFG-Projekt Ku 658/1 )

Es ist allgemein anerkannt, daß die Topologie von Mehrprozessorsystemen ein entscheidender Faktor für die Effizienz von parallelen und insbesondere VLSI-gerechten Algorithmen ist. Der Entwurf und die Analyse von Algorithmen für gitterartig verbundene Prozessorfelder ist derzeit Forschungsschwerpunkt.
Die Untersuchung von schnellen deterministischen Paket-Routing-Algorithmen auf höherdimensionalen Gittern wurde mit Erfolg fortgesetzt. Dabei zeigte sich, daß sich mit Hilfe der bei unterschiedlichen Problemstellungen gewonnenen Methoden und Beweismitteln (Informationssammeln durch Sortieren, geordnete Informationsverteilung, Lastbalancierung, überlapptes Arbeiten) sehr schnelle Algorithmen entwerfen lassen, deren Schrittzahl in der Nähe der einfachen Distanzschranke liegt. Weiterhin wurde unter dem Gesichtspunkt der Einfachheit bei gleichzeitiger hoher Effizienz eine Klasse von Routingverfahren entwickelt und untersucht, bei der ankommende Pakete sofort weitergeschickt werden. Bisher durchgeführte Simulationen lassen ausgezeichnete Leistungen erwarten. Für kleine Gittergrößen konnte das gute Verhalten der pulsierenden Algorithmen analytisch bestätigt werden.
Im Rahmen der Untersuchungen zum Vergleich unterschiedlicher Routingstrategien wurde die Entwicklung exakter mathematischer Modelle fortgesetzt. Dabei konnte mit dem sogenannten "Restricted Message-Routing" ein Verfahren entwickelt werden, das nur mit lokaler Kommunikation auskommt (im Gegensatz zu sonst üblichen Verfahren). Sowohl für dieses Verfahren als auch für das "Wormhole-Routing" konnten untere Schranken für den schlechtesten Fall gezeigt werden, die sich leider als recht ungünstig erwiesen. Bisher durchgeführte Simulationen lassen jedoch ein wesentlich besseres Ergebnis für das Verhalten im Mittel erwarten.
Die Arbeiten an systolischen Algorithmen für das Tensorprodukt und speziellen Problemen der Bilderkennung wurden abgeschlossen. (Mit: M. Schimmler, Universität Kiel, H. Schröder und E.Y. Krishnamurthy, Australian National University, Canberra, A. Maeder und B. Pham, Monash University, Melbourne).



SFB 342, Teilprojekt A4 "KLARA"

Untersuchungsbereich Vererbbarkeit:

Heckner, Lange, Riedle, Gomm

Es wurde ein synchrones Modell ("Der lange Weg") zur Darstellung paralleler Algorithmen erarbeitet und seine effiziente Einbettung auf asynchronen Rechnern mit verteiltem Speicher vorbereitet.


Jenner, Lange, Rossmanith

Grundlagen einer adäquaten parallelen Komplexitätstheorie zur Klassifikation von Algorithmen, die effizient auf dem synchronen Modell "Der Lange Weg" dargestellt werden können, wurden erarbeitet.


Untersuchungsbereich Charakterisierung:

Niedermeier, Rossmanith:

Ergebnisse über eindeutige augmentierte Kellerautomaten wurden erweitert durch die Betrachtung von Automaten mit eingeschränkter Mehrdeutigkeit.


Niepel, Rossmanith:

Durch die Entwicklung des Begriffs eines Auswahlgatters konnten PRAMs mit exklusivem und gleichzeitigen Speicherzugriffen durch Schaltnetze charakterisiert werden.


Rossmanith

In Erweiterung des owner-write Konzepts wurde das owner-read Konzept eingeführt und die engen Beziehungen zu r NC-Hierarchie aufgezeigt. Die Ergebnisse werden auf der STACS 91 präsentiert.


Jenner, Àlvarez, Balcázar:

Untersuchung eines "nicht-adaptiven" und eines "adaptiven" Modells für funktionale Orakel bei logarithmischem Platz führten u. a. zu einer neuen Charakterisierung von AC-Reduktionen und der Beantwortung offener Fragen von Wilson.
Die Ergebnisse werden auf der STACS 91 präsentiert.


Jenner, Àlvarez, Balcázar:

Fortsetzung der Arbeiten über logarithmisch platzbeschränkte "Counting"-Funktionenklassen (mit Àlvarez).
Betrachtung von Orakel-Transduktoren, denen ein gewisser Zugriff auf ihre Ausgabe gewährt wird.
Untersuchung der Eigenschaften von Funktionen der funktionalen Varianten alternativer Charakterisierungen des FL-Turingabschlusses von Klassen wie NL, NP und von Funktionen, deren Werte kleine Kolmogorow-Komplexität relativ zu ihren Argument haben (mit Balcázar)


Lange, Jenner, Rossmanith in Zusammenarbeit mit Buntrock, Würzburg:

Es wurden verschiedene Konzepte von Eindeutigkeit bei logarithmisch platzbeschränkten Turingmaschinen und AuxPDA mit Zeitschranke entwickelt. Geklärt wurden eine Reihe von Abschlusseigenschften zugehöriger Komplexitätsklassen und Beziehungen dieser Klassen untereinander und zu "Klassen mit wenig Berechnungspfaden".
Ferner wurden neue Erkenntnisse über die Komplexität eindeutig linearer Sprachen gewonnen.


Lange, Dassow (TU Magdeburg)

Die für viele Automatenmodelle bekannte Beziehung zwischen Wortproblem des Zweiwegautomaten und Leerheitsproblem des Einwegautomaten konnte allgemein für das abstrakte Automatenmodell von Engelfriet gezeigt werden.


Lange, Reinhardt (Univ. Stuttgart)

Als Einschränkung der allgemeinen Alternierung wurde der Begriff der leeren Alternierung eingeführt. Mit seiner Hilfe konnten NC-, AC- und P[log n]-Klassen charakterisiert werden.


Untersuchungsbereich Heuristik:

Brombacher, Lange, Niedermeier

Es wurden verschiedene Heuristiken zur Abarbeitungsreihenfolge der Variablen in der Davis-Putnam-Prozedur betrachtet. Darauf aufbauend wurde die Korrelation zwischen verschiedenen Strukturparametern von Formeln und der Größe des dazugehörigen Baumes untersucht.


Lange in Zusammenarbeit mit Goerdt, Universität Duisburg

Die Analysen durch Speckenmeyer von "Superlinear Speedup"-Phänomenen bei parallelen Erfüllbarkeits-Heuristiken wurden auf quantifizierte Formeln erweitert.


Hoffmann, Kalkhoff, Lange, Modlich (Teilprojekt B1 "Parallelisierung von Entwurfsverfahren für höchstintegrierte Schaltungen")

Es wurden drei parallele Algorithmen in den Bereichen Plazierung und Routing entwickelt, implementiert und auf ihre Effizienz hin untersucht.



DFG-Projekt La 618 1-1 "Unär"

Niepel

Es wurden Beziehungen zwischen unaeren Mengen und Schaltnetzen bzw. Schaltnetzreduktionen untersucht. Ausserdem erfolgten Charakterisierungen von Reduktionen durch Sprachen und Operatoren.


Holzer, Kirtz, Lange, Niepel

Ausgehend von Standardtranslationsphänomenen zwischen linearem und logarithmischem Platzbedarf, wurden Verallgemeinerungen in Richtung alternierender und sequentieller Zeit sowie in Richtung höherer Komplexitätsschranken untersucht. In beiden Fällen müssen adäquate Reduktionstypen gefunden werden.



2.2 Weitere Forschungsvorhaben

Brauer, Gold, Vogler:
Verschiedene in der Literatur existierende Konzepte zum hierarchischen Entwurf verteilter Systeme mittels Verfeinerung von Petrinetzen wurden miteinander verglichen.

Brauer, Schill (Inst. für Med. Psychologie, LMU), Schuster:
Konzeption und Implementierung einer Wissensbasis unter Einbezug der strukturellen Abhängigkeiten von Expertenwissen.

Desel:
Forschungsarbeiten zu Free-Choice Petri-Netzen, Charakterisierung von Erreichbarkeit und von Grundzuständen in Free-Choice Netzen, Syntheseverfahren für Teilklassen, Bezug zwischen Free-Choice Netzen und Bipolaren Schemata.

Diekert, Ispas-Muscholl, Lange:
Aufbauend auf Ergebnissen von McKenzy et al. wurden Darstellungen der Komplexitätsklassen NP und L durch Gruppoidähnliche Ansätze gefunden.

Diekert:
Die Arbeiten an der Monographie "Combinatorics on Traces" wurden abgeschlossen.

Diekert, Ochmanski, Reinhardt:
Es wurde gezeigt, daß die Konfluenz von Semi-Kommutationssystemen entscheidbar ist. Das entwickelte graphentheoretische Kriterium wurde alco-NP-vollständig und in allgemeiner Form als [[Sigma]]2P-vollständig nachgewiesen. Zugleich gelang die Lösung eines offenen Problems über die Synchronisierbarkeit von Mazurkiewicz-Spuren. Die Frage nach der sogenannten lokalen Überprüfbarkeit der Synchronisation erwies sich ebenfalls als Co-NP-vollständig.

Diekert:
Es wurden sogenannte partielle Spuren eingeführt. Sie können als eine Halbordnungsemantik für Stellen/Transitionssystem dienen. Partielle Spuren verhalten sich gut in Bezug auf verschiedene Netzoperationen und lassen sich algebraisch in bereits bestehende Konzepte einbetten.

Diekert:
Im Gegensatz zu unendlichen Wörtern lassen sich unendliche Mazurkiewicz-Spuren nicht unmittelbar konkatenieren, da hier eine Mischung von paralleler und sequentieller Komposition vorliegt. Um dieses Problem zu lösen, wurden die sogenannten komplexen Spuren eingeführt, die in einer zweiten Komponente Alphabetinformationen über das Grenzverhalten tragen. Im einer ersten Arbeit wurden algebraische und topologische Egenschaften der komplexen Spuren studiert.

Gold:
Durch Übertragung von Methoden aus dem Bereich der Datenflussnetze auf Petrinetze wurde eine funktionale Beschreibung des Ein-/Ausgabeverhaltens von Petrinetzen entwickelt. Es wurde u. a. die Kompositionalität dieser neuen Semantik gezeigt.

Gomm, Kindler, Reisig, Walter:
Im Rahmen der SFB-Kooperation wurde begonnen, das Mailboxkonzept im MMK und das Konzept eines virtuellen gemeinsamen Speichers mit Petri Netzen zu spezifizieren und verifizier

Hernández:
Bei der Untersuchung qualitativer Repräsentationen räumlichen Wissens wurde für den Spezialfall der 2- D Projektion 3- D Szenen eine kleine Anzahl von Relationen aus den Projektions- und Richtungsdimensionen definiert.
Die "konzeptuellen Nachbarschaften" dieser Relationen (die sich aus den "physikalischen" Nachbarschaften der durch sie beschriebenen Situationen ableiten lassen) können vorteilhaft zur Orientierung der auf den Relationennetz operierende Suchalgorithmen benutzt werden. Diese lassen sich unter die klasse der "constraint satisfaction" Algorithmen einordnen.

Lange, Seifried:
Für das Leerheitsproblem des Schnitts regulärer Mengen wurde die Anzahl der beteiligten Automaten funktional begrenzt. Auf diese Weise konnten vollständige Probleme für NSPACE(f) und NTISP(POL,f) für sublineares f gefunden werden.

Reisig:
Grundfragen zu nicht-sequentiellen Systemen und zur Systematik im Bereich der Petrinetze und denen Einbettung in die geamte Informatik.

Schätz:
Es wurden vorhandene analogische Repräsentationsformen untersucht, und formale Charakterisierungen entwickelt. Darauf aufbauend wurden analogische Lösungsverfahren hinsichtlicher der ihnen zugrundeliegenden strukturdefinierten Ähnlichkeitsbeziehungen charakterisiert, und implizite Annahmen herausgearbeitet.

Schmidhuber:
Lernen von Roboterbewegungssequenzen mit neuronalen Netzen, Neuronale Systeme zur adaptiven Dekomposition und Abstraktion von Ereignisfolgen, Adaptive neuronale Subzielgenerierung.

Schoett:
Es wurde gezeigt, daß das Verbot unbeobachtbarer Gleichungen in der Prädikatenlogik erster Stufe es unmöglich macht, einen Zähler endlich zu spezifizieren. Daher benötigen beobachtungsorientierte Spezifikationssprachen stärkere Sprachmittel als die der Prädikatanlogik erster Stufe. Auch erweist sich damit die bisher bekannte Ableitungsregel für die beobachtungsorientierte Semantik von Spezifikationen in dieser Logik als zu schwach.

Vogler:
Die Untersuchungen zur Aktionsverfeinerung bei Petrinetzen und Ereignisstrukturen wurden fortgesetzt. Zwei verschiedene Darstellungen für auf Intervall-Ordungen gestützte Petrinetz-Semantiken wurden verglichen und ein neues Entscheidbarkeitsresultat erzielt. Es wurden zu verschiedenen Semantiken vom Bisimulationstyp Varianten entwickelt, die Kongruenzen bzgl. Aktionsverfeinerung induzieren. Ferner wurde eine neue Darstellung für die prozeßfortsetzende Bisimulation gefunden, die ein Entscheidungsverfahren für sichere Netze ermöglicht.

Walter:
Anhand konkreter Fallbeispiele wurden Beweisregeln zur korrekten Spezifikationsverfeinerung entwickelt, so daß die Gültigkeit resultierender lokaler temporallogischer Anforderungen für ein gegebenes Petri-Netz System elementar überprüfbar ist.

Weiß:
Untersuchungen zum maschinellen Lernen in verteilten Systemen






3 Veröffentlichungen

Àlvarez, C., Balcázar, J.L., and Jenner, B. : Functional oracle queries as a measure of parallel time. Tech. Rept. LSI-90-24, Universitat Politècnica de Catalunya, Dept. L.S.I., Barcelona, November, 1990.

Best, E., Cherkasova, L., Desel, J., and Esparza, J. : Characterisation of Home States in Free Choice Systems. Tech. Rept. 9/90, Hildesheimer Informatikberichte, Universität Hildesheim, September, 1990.

Best, E., Cherkasova, L., Desel, J., and Esparza, J. : Traps, Free Choice and Home States. In Proceedings of the International BCS-FACS Workshop Semantics for Concurrency, Kwiatkowsa, M.Z., Shields, M.W., and Thomas, R.M., Springer, Juli 1990, pp. 16-20.

Best, E. and Desel, J. : Partial Order Behaviour and Structure of Petri Nets. Formal Aspects of Computing 2, 2 (1990), 123-138.

Bräunling, P., Freksa, C., and Zimmermann, K. : The SpaceGarden Bibliography. Tech. Rept. FKI-138-90, Forschungsbericht Künstliche Intelligenz, Institut für Informatik der Technischen Universität München, Also published in: C. Freksa & C. Habel (eds.) Repräsentation und Verarbeitung räumlichen Wissens, Informatik-Fachberichte vol. 245, Springer-Verlag, Berlin 1990., August, 1990.

Bräunling, P. : Zur kontextabhängigen Objektbenennung - Ist ein großes gelbes Haus immer groß und gelb? In Workshop Räumliche Alltagsumgebungen des Menschen, Hoeppner, W., Univ. Koblenz-Landau, 8.-10. 10. 1990, pp. 1-8.

Brauer, W. and the AI/Cognition Group : Approaches to the representation of knowledge. In Advanced Information Processing. Proceedings of a Joint Symposium Information Processing and Software Systems Design Automation, Schwärzel, H. and Mizin, I., Academy of Science of the USSR and Siemens AG, Springer, Berlin, 6 1990, pp. 29-38.

Brauer, W. : Graphs, Automata, Petri Nets - From Sequential to Distributed and Concurrent Systems - . In Advanced Information Processing. Proceedings of a Joint Symposium Information Processing and Software Systems Design Automation, Schwärzel, H. and Mizin, I., Academy of Science of the USSR and Siemens AG, Springer, Berlin, 6 1990, pp. 15-28.

Brauer, W. : Trends der Informatikausbildung, In A. Reuter (Ed.) GI - 20. Jahrestagung I, IFB 257, Springer-Verlag, Berlin 1990, pp. 456-464

Brauer, W. : Gezeichnete Beiträge zum "Lexikon der informatik und Kommunikationstechnik", F. Krückeberg und O. Spaniol (eds.), VDI-Verlag, Düsseldorf, 1990

Deffner, R., Geiger, H., Kahler, R., Krempl, T., and Brauer, W. : Recognizing Words with Connectionist Architectures. In Proceedings of INNC 90, vol I, Paris, 1990, pp. 196 ff.

Desel, J. : Reduction and Design of Well-behaved Concurrent Systems. In Proceedings of CONCUR'90, LNCS 458, Baeten, J.C.M. and Klop, J.W., Springer, 8 (1990), pp. 166-181.

Desel, J. and Esparza, J. : Reachability in Reversible Free-Choice Systems. Tech. Rept. SFB-Bericht 342/11/90 A, TU München, Juni, 1990.

Desel, J. and Merceron, A. : P/T-systems as abstractions of C/E-systems. In Advances in Petri Nets 1989. Springer, Rozenberg, G., pp. 105-127, 1 (1990).

Desel, J. : On Abstractions of Nets. Tech. Rept. SFB-Bericht 342/2/90 B, TU München, 4, 1990.

Desel, J. : Reduction and Design of Well-behaved Free-choice Systems. Tech. Rept. SFB-Bericht 342/3/90 B, TU München, 5, 1990.

Desel, J., Reisig, W., and Walter, R. : The Alternating Bit Protocol Fairness Versus Priority. Petri Net Newsletter 35 , 4 (1990), 3-5, published by Gesellschaft für Informatik.

Diekert, V. : Two contributions to the theory of Mazurkiecwicz traces. Tech. Rept. TUM-I9043, TU München, Institut für Informatik, 1990.

Diekert, V. : Combinatorial rewriting on traces. In Proc. of the 7th Annual Symposium on Theoretical Aspects of Computer Science (STACS 90), Choffrut, C., Springer, 1990, pp. 138-151.

Diekert, V. : Combinatorics on Traces, Springer , Vol. 454, Lecture Notes in Computer Science(1990).

Diekert, V., Ochmanski, E., and Reinhardt, K. : On confluent semi-commutations - Decidability and complexity results. Tech. Rept. TUM-I9041, TU München, Institiut für Informatik, 1990.

Diekert, V. : Research topics in the theory of free partially commutative monoids, Springer, Vol. 40, EATCS-Bulletin (1990)pp. , 479-491.

Diekert, V. : (ed.) Proc. of the Workshop "Free Partially Commutative Monoids", Institut für Informatik, TU München, Tech. Rept. TUM-I-9002, 1990

Diekert, V. : Word problems over traces which are solvable in linear time. Theoret. Comp. Science (Sonderband STACS 89) 74 (1990), 3-18.

Dorigo, M. and Schätz, B. : Mapping a Simulator for Neural Networks to a Transputer System. Tech. Rept. FKI-137-90, Technische Universität München, Oktober, 1990.

Freksa, C., Bräunling, P., and Zimmermann, K. : The SpaceGarden interface for an interdisciplinary bibliography system. Tech. Rept. TU München, Institut für Informatik, 1990.

Freksa, C. : Cognitive Science -- eine Standortbestimmung. Universitas 525 (März 1990), 232-240.

Freksa, C. and Habel, C. (Hg.). : Repräsentation und Verarbeitung räumlichen Wissens. Springer, Berlin, 1990.

Freksa, C. and Habel, C. : Warum interessiert sich die Kognitionsforschung für die Verarbeitung räumlichen Wissens?. In Repräsentation und Verarbeitung räumlichen Wissens. Springer, Berlin, Freksa, C. and Habel, C., pp. 1-15, 1990.

Freksa, C. : Qualitative spatial reasoning. In Workshop Räumliche Alltagsumgebung des Menschen, Hoeppner, W., Universität Koblenz-Landau, Oktober 1990.

Freksa, C.: Temporal Reasoning based on semi-intervals. Tech. Rept. Report TR-90-016, International Computer Science Institute , Berkeley, California, 1990.

Freksa, C. : Wissensarten und Kognitionsforschung. In Wissensrepräsentation. Oldenbourg, Struß, P., pp. 61-68, 1990.

Gold, R. and Vogler, W. : Quality criteria for partial order semantics of place/transition nets.. In Proc. of the 15th Symposium on Mathematical Foundations of Computer Science, Rovan, B., Springer, Banska Bystrica, 1990, pp. 306-312.

Gold, R. and Vogler, W : Quality criteria for partial order semantics of place/transition-nets.Tech. Report TUM-I9004, August 1990.

Gomm, D. and Walter, R.: The Distributed Termination Problem: Formal Solution and Correctness Based on Petri Nets. In Aspects and Prospects of Theoretical Computer Science. Springer-Verlag, Dassow, J. and Kelemen, J., (Rds.) pp. 159-168, 1990.

Wirtz, G., Gomm, D., Jostmeier, K., and Ruppelt, T.: SUSPENSE - Specification and Transformation of Multigrid Algorithms. Research Report 900101, Institut für Informatik, Universität Bonn, Januar1990.

Hernández, D.: Relative Representation of Spatial Knowledge: The 2-D Case. In Cognitive and linguistic aspects of geographic space. Kluwer, Dordrecht, Mark, D.M. and Frank, A.U., 1990.

Jantzen, M., Kudlek, M., Lange, K.J., and Petersen, H. Dyck :1-Reductions of Context-Free Languages. Comp. and Artif. Intel. 9 (1990), 3-18.

Klöck, E.: Erst Denken, dann Sprechen? - Die kognitive Basis der Sprachproduktion. In Workshop Räumliche Alltagsumgebung des Menschen, Höppner, W., Universität Koblenz-Landau, 1990, pp. 92-101.

Krishnamurthy, E.V., Kunde, M., Schimmler, M., and Schröder, H.: Systolic algorithm for tensor products of matrices - implementation and applications. Parallel Computing 13(1990), 301-309.

Kunde, M. and Tensi, T.: Bounds for Obvious Message Routing on Grids. In PARCELLA 90, Proc. of the V. International Workshop on Parallel Processing by Cellular Automata and Arrays, Wolf, G., Akademie-Verlag Berlin, Sept. 17-21 1990, pp. 227-238.

Lange, K.- J.: Unambiguity of Circuits. In Proceedings of "Structure in Complexity Theory" IEEE CSP 2072, pp. 130-137, 1990

Lange, K.-J. and Rossmanith, P.: Characterizing unambiguous Augmented Push-down Automata by Circuits. In Proceedings of the15th MFCS, 1990, pp. 299-406.

Lange, K.-J. and Rossmanith, P.: Two Results on Unambiguous Circuits. Tech. Rept. TUM-I9006, SFB-Bericht 342/3/90 A, TU München, Institiut für Informatik, 1990.

Niedermeier, R. and Rossmanith, P.: Unambiguous Simulations of Auxiliary Pushdown Automata and Circuits. Tech. Rept. TUM-I 9054, SFB-Bericht 342/31/90 A, TU München, Institut für Informatik, 1990.

Niepel, I. and Rossmanith, P.: Uniform Circuits and Exclusive Read PRAMs. Tech. Rept. TUM-I9055, SFB-Bericht 342/32/90 A, TU München, Institut für Informatik, 1990.

Rossmanith, P.: The Owner Concept for PRAMs. In Proceedings of the 8th STACS, 1991, pp. 172-183

Schätz, B.: Portierung eines neuronalen Netzwerksimulators auf ein Transputersystem. In Abstraktband des 2. bundesweiten Transputer-Anwender-Treffens TAT'90, et a ., R.G., RWTH Aachen , Aachen , 17./18. 09 1990, pp. 48-49.

Schätz, B.: Ein konnektionistischer Ansatz zur verteilten Darstellung von Objektpositionen. In Workshop Räumliche Alltagsumgebungen des Menschen, Hoeppner, W., Univ. Koblenz-Landau, 8.-10. 10. 1990, pp. 147-158.

Schoett, O.: Behavioural correctness of data representations. Science of Computer Programming 14(1990), 43-57.

Schimmler, M., Schröder, H., Kunde, M., Maeder, A., and Pham, B.: A Linear Array of Rings for Local Operations in Immage Processing. In Proc. of International Conference on Automation, Robotics and Computer Vision, McGraw-Hill, Singapore - New York, 1990, pp. 973-977.

Schmidhuber, J.H.: A Local Learning Algorithm for Dynamic Feedforward and Recurrent Networks. Connection Science 1, 4 (1990), 403-412.

Schmidhuber, J.H.: Recurrent Networks Adjusted by Adaptive Critics. In Proc. IEEE/INNS International Joint Conference on Neural Networks,Washington, D. C., 1990, pp. 719-722.

Schmidhuber, J.H.: Networks Adjusting Networks. In Proceedings of 'Distributed Adaptive Neural Information Processing', St.Augustin, 24.-25.5. 1989 , Kindermann, J. and Linden, A., Oldenbourg, In November 1990 a revised and extended version appeared as FKI-ReportFKI-125-90 (revised) at the Institut für Informatik, Technische Universität München, 1990, pp. 197-208.

Schmidhuber, J.H.: Temporal-Difference-Driven Learning in Recurrent Networks. In Parallel Processing in Neural Systems and Computers. North-Holland, Eckmiller, R., Hartmann, G., and Hauske, G., pp. 209-212, 1990.

Schmidhuber, J.H.: Response to 'G. Lukes' review of 'Recurrent networks adjusted by adaptive critics'. Neural Network Review, in press (1990).

Schmidhuber, J.H.: Reinforcement-Lernen und adaptive Steuerung. Nachrichten Neuronale Netze 2(1990), 1-3.

Schmidhuber, J.H.: Making the world differentiable: On Using Fully Recurrent Self-Supervised Neural Networks for Dynamic Reinforcement Learning and Planning in Non-Stationary Environments. Tech. Rept. FKI-126-90 (revised)Institut für Informatik, Technische Universität München, (Revised and extended version of an earlier report from February.) , November, 1990.

Schmidhuber, J.H.: An On-Line Algorithm for Dynamic Reinforcement Learning and Planning in Reactive Environments. In Proc. IEEE/INNS International Joint Conference on Neural Networks, San Diego, 1990, pp. 253-258.

Schmidhuber, J.H.: Reinforcement Learning with Interacting Continually Running Fully Recurrent Networks. In Proc. INNC International Neural Network Conference,Paris, 1990, pp. 817-820.

Schmidhuber, J.H. and Huber, R.: Learning to Generate Focus Trajectories for Attentive Vision. Tech. Rept. FKI-128-90Institut für Informatik, Technische Universität München, 1990.

Schmidhuber, J.H.: Towards Compositional Learning with Dynamic Neural Networks. Tech. Rept. FKI-129-90, Institut für Informatik, Technische Universität München, 1990.

Schmidhuber, J.H.: Learning Algorithms for Networks with Internal and External Feedback. In Proc. of the 1990 Connectionist Models Summer School, in press, San Mateo, CA: Morgan Kaufmann, 1990.

Schmidhuber, J.H.: A Possibility for Implementing Curiosity and Boredom in Model-Building Neural Controllers. In Proc. of the International Conference on Simulation of Adaptive Behavior: From Animals to Animats, in press, MIT Press/Bradford Books, 1990.

Schmidhuber, J.H.: Dynamische neuronale Netze und das fundamentale raumzeitliche Lernproblem, Ph.D. dissertation, Institut für Informatik, Technische Universität München, 1990.

Vogler, W.: A generalization of trace theory. Tech. Rept. TUM-I9018, TU München, Institut für Informatik, 1990.

Vogler, W.: Bisimulation and action refinement. Tech. Rept. SFB-Bericht, 342/10/90 A, TU München, Institut für Informatik, 1990.

Vogler, W.: Failures semmantics based on interval semiwords is a congruence for refinement. In Proc. of STACS 90, C.Choffrut et al. (eds.), Rouen, Springer, Febr. 1990, pp. 285-297.

Vogler, W.: On hyperedge replacement and BNLC graph grammars. In Proc. of the 15th Int. Workshop in Graph-Theoretic Concepts in Computer Science WG'89, Nagl, M. (ed.), Castle Rolduc, Springer, 2 1990, pp. 78-93.

Vogler, W.: Recognizing edge replacement graph languages in cubic time. Tech. Rept. TUM-I9017, TU München, Institut für Informatik, 1990.

Vogler, W.: Representation of a swapping class by one net. In Advances in Petri Nets 1989. Rozenberg G. (ed.), Springer, pp. 467-486, 1990.

Waschulzik, T., Geiger, H., Arnoldi, M., Böller, D., Nischwitz, A., and Brauer, W.: New Concepts for Information Processing in Connectionistis Systems. In Parallel Processing in Neural Systems and Computers. Amsterdam, Eckmiller, R., Hartmann, G., and Hauske, G., pp. 323-328, 1990.

Weiß, G.: Artificial Neural Learning. Tech. Rept. FKI-127-90, TU München, 2, 1990.

Weiß, G.: Combining neural and evolutionary learning: Aspects and approaches. Tech. Rept. FKI-132-90, TU München, 5, 1990.

Zimmermann, K.W.: Entwicklung einer bildorientierten Benutzungsoberfläche für wissensbasierte Dialogsysteme. Tech. Rept. FKI-134-90, Forschungsberichte Künstliche Intelligenz, Institut für Informatik, Technische Universität München, München, To appear in K.Kansy und P. Wißkirchen (Hrsg.), Graphik und KI, Informatik-Fachberichte 239, Springer, Berlin, April 1990., Januar, 1990.

Zimmermann, K.W.: Entwicklung einer bildorientierten Benutzungsoberfläche für wissensbasierte Dialogsysteme. In Graphik und KI, Kansy, K. and Wißkirchen, P., Gesellschaft für Informatik, Springer, Berlin, April 1990, pp. 10-18.

Zimmermann, K.W.: Entwicklung einer bildorientierten Benutzungsoberfläche für wissensbasierte Dialogsysteme. In Graphik und KI, Kansy, K. and Wißkirchen, P., Gesellschaft für Informatik, Springer, Berlin, 4 1990, pp. 10-18.




4 Vorträge

Brauer

Bräunling

Desel

Diekert

Freksa

Gold

Gomm

Heise

Hernández

Jenner

Kindler

Kunde

Lange

Reinhardt

Reisig

Rossmanith

Schätz

Schoett

Tensi

Vogler

Walter






5 Vorlesungen und Seminare

Brauer, Hernández Brauer, Freksa, Hernández Brauer, Freksa, Schmidhuber, Weiß Brauer, Freksa, Bernasch, Schmidhuber Brauer, Freksa, Laußermaier, Weiß Brauer, Freksa, Schätz Diekert Diekert, Kunde, Lange, Jenner, Rossmanith, Tensi Gomm, Reisig Reisig Desel, Walter Lange Lange, Kunde Lange, Kunde, Tensi




6 Sonstige Tätigkeiten

Brauer Desel Diekert Freksa Gold Gomm Heise Hernández Jenner Klöck Kunde Lange Reisig Schmidhuber Schoett Tensi Vogler Walter


Martin Eldracher, eldrache@informatik.tu-muenchen.de, 1995-12-15