Tätigkeitsbericht 1992

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. Lehrbeauftragte
    7. Drittmittel
  2. Darstellung der Forschungsvorhaben
    1. Projekte
    2. Weitere Forschungsvorhaben
  3. Veröffentlichungen
  4. Vorträge
  5. Vorlesungen und Seminare
  6. Sonstige Tätigkeiten
  7. Forschungsberichte Künstliche Intelligenz
  8. Rufnummern/E-Mail-Adressen

1 Mitglieder

1.1 Professoren

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


1.2 Wissenschaftliche Mitarbeiter

Dr. Jörg Desel wiss. Angestellter bis 31.3.92, seit 1.4.92 wiss. Assistent
Dr. Daniel Hernández wiss. Angestellter
Dr. Birgit Jenner wiss. Assistentin, seit 7.7.92 im Erziehungsurlaub, ab 1.10.92 Forschungsaufenthalt am Dept. L.S.I der Univesitat Politècnica de Catalunya in Barcelona, Spanien mit Habilitationsstipendium der DFG
Dr. Astrid Kiehn wiss. Assistentin
Dr. Manfred Kunde Oberassistent seit 15.6.92
Oliver Schoett, Ph.D. Akad. Rat; vom 01.02.92-31.07.92 beurlaubt für Forschungsaufenthalt in Swansea/Großbritannien
Dr. Walter Vogler Oberassistent; bis 31.03.92 beurlaubt wegen einer Vertretungsprofessur an der LMU München, seit 01.10.92 Universitätsprofessor an der Universität Augsburg
Carsten Damm wiss. Angestellter, bis 31.03.1992
Martin Eldracher wiss. Angestellter
Robert Gold wiss. Angestellter
Dominik Gomm wiss. Angestellter
Andreas Heise wiss. Angestellter
Marcus Holzer wiss. Angestellter
Margit Kinder wiss. Angestellte
Ekkart Kindler wiss. Angestellter
Angelika Mader wiss. Angestellte
Rolf Niedermeier wiss. Angestellter
Peter Rossmanith wiss. Angestellter
Rolf Walter wiss. Angestellter
Gerhard Weiß wiss. Angestellter
Dieter Barnard Siemens-Stipendiat
Kai Zimmermann nebenberufliche wiss. Hilfskraft bis 30.3.92

1.3 Sekretärinnen

Ingeborg Biberger
Paula Grylka


1.4 Studentische Hilfskräfte

Till Brychcy Projektbezogene Programmierarbeiten (NERES), Softwarebetreuung (Mac, UNIX)
Rolf Großmann Stoftwarebetreuung (TeX, gcc), Hardware-betreuung
Christian Guenther Pflege, Beratung und Vorführung von Petrinetzwerkzeugen, Mitarbeit bei Fallstudien seit 01.11.92
Gabriela Hess Pflege, Beratung und Vorführung von Petrinetzwerkzeugen, Mitarbeit bei Fallstudien von 01.04.92 bis 31.08.92
Kerstin Jäschke Literaturbeschaffung und -verwaltung, Textverarbeitung, Büroorganisation bis 31.03.92
Daniel Kobler Projektbezogene Programmierarbeiten (NERES)
Viola Krings Literaturbeschaffung und -verwaltung, Text-verarbeitung, Büroorganisation seit 01.08.92
Gerd Pauli Hard- und Software-Betreuung (Unix)
Marcus Peisker Systemadministration seit 01.04.92
Doris Reisenauer Literaturbeschaffung und -verwaltung, Textverarbeitung, organisatorische Tätigkeiten seit 01.06.92
Dirk Rodemer Softwarebetreuung (email)
Thomas Röll Hard- und Softwarebetreuung (Unix) bis 31.07.92
Aenne Scharbert Pflege, Beratung und Vorführung von Petrinetzwerkzeugen, Mitarbeit bei Fallstudien

1.5 Gäste

01.02. - 31.08.92 J. F. Traub (Columbia University New York)
Alexander von Humbold-Forschungspreisträger

01.02. - 31.08.92 Pamela McCorduck (New York, Princeton)
International renommierte Autorin: Bücher über Informatik, Künstliche Intelligenz und Kunst

09.01.92 J. Schmidhuber (Boulder, Colorado)
Neue Methoden für unüberwachte Regularitätsentdeckungen in Eingaben oder Eingabesequenzen für normale Netzwerke

22.01.92 Ch. Ebert (TU Stuttgart), H. Oswald (Landis & Gyr Zug AG)
Petrinetze in der Automatisierungstechnik

23.01.92 W. Büttner (Siemens AG München)
Zuverlässigkeit neuronaler Lernalgoithmen

12.02.92 T. Waschulzik (GSF, München), B. Protzl (FORWISS, Erlangen)
Anwendungen von Kohonenmaps

12.02.92 Wolf Zimmermann (Universität Karlsruhe)
Automatische Komplexitätsanalyse funktionaler Programme

20.02.92 R. Kirkova (Sofia)
Multimedia- und Hypertext-Grundlage bei der Informationsverwaltung

09.03. - 14.03.92 Bernd Kirsig (Universität Hamburg)
Komplexitätstheorie im logarithmischen Platzbereich

19.03.92 C. Freksa (Universität Hamburg)
Qualitative Aspekte der Raumrepräsentation

10.04.92 H.-P. Schwefel (Universität Dortmund)
Kollektive Problemlösung mittels künstlicher Evolution

25.05.92 O. Dressler (Siemens AG, München)
Nicht-monotone Begründungsverwaltungssysteme

10.06.92 David Murphy (GMD Bonn)
Intervals and Actions in a Timed Process Algebra

16.06.92 Lane A. Hemachandra (University of Rochester)
Promise Problems and Access to Unambiguous Computations

24.06.92 Beninghofen (MBB München), A. Sacher
Effiziente Erstellung von VORONOI - Diagrammen

02.07.-04.07.92 Colin Stirling (University of Edinburgh)
Logic + Fixed Points = Program Logic

02.07.92 J. Hollatz (Siemens, München)
Netzwerk-Strukturierung durch unsichere Regeln

01.09.-08.09.92 Julian Bradfield (University of Edinburgh)
Model Checking in the Modal Mu-Calculus for Infinite State Spaces

30.09.92 J. Cunningham (Imperial College London)
Hybride Systeme

05.11. - 12.11.92 Dr. E. Smith (GMD, Bonn)

02.12. - 04.12.92 Massimiliano Goldwurm (Universität Mailand)
Ranking of Context-free Languages

07.12. - 09.12.92 Denis Therien (McGill University, Montreal)
Circuits, Regular Languages, and Formulas

07.12. - 11.12.92 Heiko Schröder (University of Newcastle, Australien)
A Load Balancing Model on the Mesh

09.12.92 Anca Muscholl (Universität Stuttgart)
Deterministische asynchrone Automaten für Sprachen von unendlichen Spuren

09.12. - 11.12.92 Ulrich Hertrampf (Universität Trier)
Locally Definable Acceptance Types

12.12.-16.12.92 Javier Esparza (Universität Hildesheim)
Model Checking Using Net Unfoldings

15.12. - 18.12.92 Andreas Goerdt (Universität-Gesamthochschule Paderborn)
Zur mittleren Laufzeit von Erfüllbarkeitsalgorithmen

16.12.92 J. Pfalzgraf (RISC, Linz)
Kategorientheorie und Neuronale Netze

17.12.92 C. Habel (Universität Hamburg)
Verarbeitung räumlichen und zeitlichen Wissens


1.6 Lehrbeauftragte

Dr. D. Taubner, Siemens ZFE
Dr. M. Payer, Siemens ZFE
Dr. H. Geiger, Kratzer Automatisierung


1.7 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 "Unäre Sprachen im unteren Komplexitätsbereich" (La 618/1-1)

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

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

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

ESPRIT BRA Working Group No 6067 CALIBAN: "Casual 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" (FKZ ITN9102B)






2 Darstellung der Forschungsvorhaben

2.1 Projekte

SFB 0342, Teilprojekt A3 SEMAFOR (Leitung: Brauer, Reisig)

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

In diesem Projekt werden Formalismen zum Umgang mit verteilten, reaktiven Systemen entwickelt. Dabei wird insbesondere untersucht, wie weit Kenntnisse über Verteiltheit und Unabhängigkeit von Systemkomponenten helfen, Systeme zu spezifizieren, zu entwerfen und zu analysieren. Methodisch werden dabei zwei Entwicklungslinien zusammengebracht: Ansätze, die verteilte, reaktive Systeme im wesentlichen mit herkömmlichen, für den sequentiellen Fall entwickelten Techniken beschreiben und analysieren, und andererseits solche Ansätze, die Nebenläufigkeit als eine Grunderscheinung von Systemen überhaupt ansehen.
Die im Teilprojekt entwickelte Spezifikations- und Beweislogik wurde in Fallstudien getestet und ergab interessante Resultate. Insbesondere konnten für ausgewählte Beispiele Eigenschaften bewiesen werden, die mit anderen temporalen Logiken nicht gezeigt werden können. In der Kooperation mit SIEMENS wurden Protokolle zur Organisation virtuell gemeinsamer, physikalisch verteilter Speicher spezifiziert und als korrekt bewiesen.



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

Dieses Teilprojekt bemüht sich um eine adäquate komplexitätstheoretische Modellierung paralleler Berechnungen.


Lange, Niedermeier

Untersuchungen in Hinblick auf Kommunikationsstrukturen von parallelen Registermaschinen (PRAM's) und deren Unabhängigkeit von der Eingabe (welches eine wichtige Eigenschaft für die effiziente Implementierung auf Rechnern mit verteiltem Speicher darstellt) wurden fortgesetzt. Insbesondere wurde eine Charakterisierung der Komplexitätsklassen NCk, DSPACE(log n) und LOGDCFL nicht nur über PRAM's mit strukturell beschränkten Kommunikationseigen-schaften, sondern auch über ein Maschinenmodell mit in gewisser Hinsicht "eingebauter" Datenunabhängigkeit (INDEX-PRAM's) erreicht.



Niedermeier, Rossmanith

Es wurde untersucht inwieweit Funktionen, die durch Rekursionsgleichungen definiert sind, effizient parallel ausgewertet werden können. Dabei konnten optimale Algorithmen für das sehr eingeschränkte OROW Modell gefunden werden, die zudem einen hohen Parallelitätsgrad erlauben.



Niedermeier, Rossmanith:

Die Möglichkeit des gleichzeitigen Schreibens und Lesens bei parallelen Brechnungen wurde mit besonderer Berücksichtigung des CREW Modells erörtert. Wir untersuchten, für welche Funktionen dies Zeitvorteile bietet und schätzten diese quantitativ ab. Auch andere verwandte Modelle wurden in dieser Hinsicht untersucht.



Rossmanith, Rytter

Für das parallele Erkennungsproblem eindeutiger kontextfreier Sprachen wurden einfachere Algorithmen entwickelt. Dabei konnte auch eine Reduzierung der benötigten Prozessoranzahl vorgenommen werden, wodurch der bisher effizienteste Algorithmus gewonnen wurde.



Rossmanith

Die Zeitkomplexität der Berechnung boolescher Funktionen auf verschiedenen parallelen Modellen wurde untersucht. Ziel ist eine genauere Erfassung der Zeitkomplexität, sowie neue Separierungen zwischen verschiedenen Modellen



SFB 0342 Teilprojekt Y1 (Kooperationsprojekt mit der Humboldt-Universität, Berlin)

Heise, Kindler, Reisig

Das von Prof. Starke entwickelte Analysewerkzeug PAN wird um eine graphische Oberfläche erweitert, die neben den bisher von PAN behandelten Stellen/Transitionsnetzen auch Netze mit strukturierten Marken verarbeiten kann. Damit werden die Grundlagen für eine spätere Integration von Komponenten zur symbolischen Analyse und Simulation dieser für die Praxis wichtigen Netzklasse gelegt.



ESPRIT BRA Project No 3148 DEMON "Design Methods Based on Nets" (Leitung: Brauer, Reisig)

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

Die Konstruktion reaktiver Systeme ist in drei Phasen zerlegbar: Die Spezifikationsphase, mit i.a. nicht-operationellen Systembeschreibungen, die Entwurfsphase mit Hardware- und Softwareunabhä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. Für Systembeschreibungen der Spezifikationsphase wurde ein temporallogischer Kalkül entwickelt, der die Spezifikation von Lebendigkeits-, Sicherheits- und Fairnesseigenschaften erlaubt. Dieser Kalkül wird interpretiert über Petrinetze, die als formales Modell der Entwurfsphase verwendet werden. Er erlaubt die modulare Komposition von Teilen des Systems unter Erhaltung der jeweiligen Systemeigenschaften. Die Adäquatheit des Kalküls wurde durch einige Fallbeispiele nachgewiesen.



ESPRIT Projekt CALIBAN (Leitung: Desel)

Brauer, Desel, Kindler, Reisig; Vogler (Universität Augsburg)

Für die Repräsentation verteilter Systeme unterscheidet man Modelle, die an der physikalisch / logischen Struktur eine Systems orientiert sind - z.B. Petrinetze - und zustandsorientierte Modelle - z.B. Transitionssysteme oder Zustandsgraphen von Petrinetzen. Beziehungen zwischen diesen Modellklassen wurden untersucht. So wurden Verfahren entwickelt, die für ein gegebenes Transitionssystem die dazugehörigen Petrinetze zu synthetisieren. Für eingeschränkte Petrinetz-Klassen konnten strukturelle Eigenschaften der dazugehörigen Zustandsgraphen gezeigt werden, die eine effiziente Verifikation dynamischer Systemeigenschaften erlauben.



BMFT Verbundprojekt NERES: "Neuronale Regelung und Steuerung" (FKZ ITN9102B) (Leitung: Brauer, Hernández)

Das vom BMFT für 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 zweiten Jahr bearbeiteten Aspekte des Projektes zusammengefaßt:

Eldracher, Heinzel, Baginski

Arbeiten zur neuronalen Subzielgenerierung. Es wurde eine bestehende Robotersimulationsumgebung so umimplementiert und erweitert, daß sie für die anstehenden Simulationen für bis zu sechsgelenkige feststehende Manipulatoren eingesetzt werden kann. Dabei übernimmt die Umgebung sämtliche Aufgaben der Kollisionsdetektion, Überprüfung erlaubter Stellungen und, falls gewünscht, Generierung von Teiltrajektorien sowie die graphische Ausgabe, während die Steuerung der simulierten Roboter durch neuronale Netze erfolgt. Mit Hilfe dieser Umgebung wurden erste erfolgreiche Versuche zur neuronalen Subzielgenerierung basierend auf Backpropagation-Netzen für zweigelenkige Roboter durchgeführt.



Eldracher, Schmidhuber, Dechentreiter, Prelinger

Kausalitätsdetektion und Datenkompression mit Neuronalen Netze. Neuronale Kausalitätsdetektion zur Kompression von Sequenzen wurde anhand der Erkennung gesprochener Zahlen von Null bis Zehn erprobt. Die Erkennungsraten des Wortklassifikators stiegen durch die Verwendung der Kausalitätsdetektion auf Werte bis zum Eineinhalb-fachen der Erkennungsrate ohne einer solchen Vorverarbeitung an. Das System reagiert dabei jedoch sehr sensitiv auf die Parameter. Ähnliche Ziele wie die Kausalitätsdetektion verfolgen Arbeiten zur Redundanzminimierung in der Kodierung der Eingabedaten für neuronale Netze: Eine bestimmte Information soll möglichst vorteilhaft und ressourcenextensiv dargestellt werden. Spezielle Verfahren zur neuronalen Gewinnung faktorieller Kodes, die die für viele andere Verfahren notwendige statistische Unabhängigkeit der einzelnen Kodekomponenten garantieren, wurden entwickelt. Diese Kodes können auch wiederum vorteilhaft in der Kausalitätsdetektion in langen Ereignissequenzen eingesetzt werden.



Hernández, Högg, Kobler, Schwarzer, Zimmermann

Untersuchung der diagrammatischen Aspekte qualitativer Repräsentationen von Raum. (Da analogische Datenstrukturen verwendet werden, die inhärent die Struktur der dargestellten 2 dimensionalen Domäne aufweisen, sind Mechanismen, die direkt auf eine solche 2-D Darstellung operieren, von besonderem Interesse.) Weiterhin wurde ein Verfahren zur "strukturellen Constraint Relaxation", bei dem die Struktur der relationalen Domäne für eine informierte Aufweichung von Constraints (anstatt einer arbiträren vollständigen Zurücknahme) ausgenutzt wird, anhand eines Planungsbeispiels mit topologischen Relationen ausprobiert. Schließlich wurde damit begonnen, ein Modell zur qualitativen Beschreibung von Formen zu entwickeln.



Kinder, Brychcy

Hierarchisches Planen von Trajektorien und Speichern von Trajektorien sind eng miteinander verknüpft. Geplante (Sub-)Trajektorien werden gespeichert; weiteres Planen kann sich auf gespeicherte Trajektorien stützen. Eine gute Generalisierungsfähigkeit des Trajektorienspeichers ist dabei von herausragender Bedeutung: Beliebige Trajektorien (innerhalb eines gegebenen Raumes) sollen mittels Interpolation zwischen gespeicherten Trajektorien vom Speicher geliefert werden. Es wurde gezeigt, daß topologieerhaltende, verteilte Kodierungen reellwertiger Ein-/und Ausgabegrößen in Neuronenaktivitäten die notwendige Generalisierung ermöglichen. Verschiedene solcher Kodierungen sowie Lernverfahren und Tools zur Visualisierung von Trainingsergebnissen wurden implementiert.



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

Damm, Holzer, Lange

Die Ergebnisse zur komplexitätstheoretischen Klassifizierung der DOL-Sprachen wurden verfeinert und veröffentlicht.



Holzer, Lange

Es wurden Untersuchungen zur Charakterisierung symmetrischer Komplexitätsklassen aufgenommen. Eine Abwandlung der Kleene'schen Hülle erwies sich als ein vollständiger Operator für SYMSPACE(log n).



Holzer

Das Leerheitsproblem für alternierende endliche Automaten wurde untersucht. Durch geeignete Einschränkungen entstanden natürliche vollständige Probleme für wichtige Komplexitätsklassen, wie P, NP und PSPACE. Für das Leerheitsproblem alternierender endlicher Automaten mit unärem Eingabealphabet konnte die Äquivalenz zum Leerheitsproblem für EOL Systeme, einem Problem für das bisher nicht bekannt ist, ob es NP oder PSPACE vollständig ist, gezeigt werden.



Holzer, Lange

Die Komplexität des Wortproblems für lineare LL(1) und LR(1) Sprachen wurde untersucht. Es wurde gezeigt, daß lineare LL(1) Sprachen unter DLOGTIME Reduktionen NC1 vollständig sind. Für lineare LR(1) Sprachen konnte hingegen die DSPACE(log n) Vollständigkeit, sowie von formalsprachlicher Seite die Gleichheit der Klasse der linearen LR(1) Sprachen und der Klasse der Sprachen, die von deterministischen one-way one-turn Kellerautomaten erkannt werden, gezeigt werden. Die Ergebnisse sind zur Veröffentlichung eingereicht.



Lange, Rossmanith

Die Untersuchungen zur Komplexität des Schnittleerheitsproblems regulärer Mengen wurden ergänzt und konnten veröffentlicht werden.



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 Kinder (beide TUM); Heindl, Beran (beide DLR); Schürmann, Finnoff, Hollatz, Ormoneit, Tresp (alle Siemens); Engelbrecht, Arnoldi, Waschulzik, Polzer, Quandt, Däschlein, Ehrlicher, Grothe, Spickhoff(alle GSF); Nischwitz, Kraut (beide Nachrichtentechnik); Geiger, Butz, Noack, Eder, Mayer, Sturm (alle Kratzer Automatisierung)

In Zusammenarbeit mit dem Institut für Dynamik der Flugsysteme der Deutschen Luft- und Raumfahrtgesellschaft (DLR) wurde ein neuronales System zur Klassifikation von Montagezuständen eines Industrieroboters realisiert.


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 Regel-wissen, Anwendung auf Schlußfolgerungsverfahren in verschiedenen Bereichen (rechtliche Fragen, Vorhersage von Immobilienpreis-entwicklungen, Robotersteuerung), Untersuchung von Zusammenhängen mit statistischen Verfahren und Fuzzy-Control-Systemen.


In Zusammenarbeit mit dem Lehrstuhl für Nachrichtentechnik wurde in neuronalen Netzen, die mit Single-Spike-Modellen realisiert worden waren, der Einfluß der Zeitauflösung auf das Synchronisationsverhalten untersucht.


In Zusammenarbeit mit der Arbeitsgruppe Anwendersysteme des MEDIS-Instituts des Forschungszentrums für Umwelt und Gesundheit (GSF) wurde eine Entwicklungsmethodik für die anwendungsspezifische Konstruktion von strukturierten neuronalen Netzen entworfen und an Hand von Projekten in den Bereichen Prognose von Lymphknoten-metastasen bei Magenkarzinomen, Analyse von epidemiologischen Studien, Analyse von vorverarbeiteten EKGs, 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 statischer (algebraischer) Funktionen in neuronalen Netzen entwickelt und sowohl qualitativ als auch quantitativ analysiert.



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

Brauer; Büttner, Taubner, Filkorn(Siemens); Barnard, 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.



An Algebraic Theory for Distributed Systems

Brauer, Kiehn, Hennessy, Jeffrey, Lin (letzten drei: University of Sussex, Brighton)
(Academic Research Cooperation, DAAD), seit 01.07.92

Ziel des Projekts ist die Entwicklung einer algebraischen Theorie, die es aufsetzend auf Prozeßalgebren erlaubt, strukturelle Aspekte wie Lokalität, Verteiltheit und Modularität zu beschreiben und zu analysieren. In den ersten 6 Monaten des Projekts wurden Beweissysteme für Äquivalenzen mit expliziter Berücksichtigung von Nebenläufigkeit untersucht bzw. ent-wickelt.



2.2 Weitere Forschungsvorhaben

Brauer, Hernández, Kinder, Zimmermann

Qualitative Repräsentation und Standardannahmen. Untersuchung der Beziehung zwischen den qualitativen Repräsentationsansätzen (insb. zur Repräsentation räumlichen Wissens) und dem Themenkomplex "Standardannahmen".



Brauer, Weiß

Untersuchungen zum maschinellen Lernen in verteilten Systemen (neuronale Netze, regelbasierte Systeme, Mehragenten-Systeme). Schwerpunkt hierbei bildet die Identifikation allgemeiner Prinzipien verteilten Lernens.



Brauer, Weiß, Turck, Zimny, Obermeier, Kirschnick

Untersuchungen zum Lernen von Aktionssequenzen in Mehragenten-systemen, wobei die Aspekte der Kooperation und der Koordination die Schwerpunkte bildeten.



Desel

Entwicklung von strukturellen hinreichenden und/oder notwendigen Bedingungen für Lebendigkeits- und Sicherheitseigenschaften allgemeiner Petrinetze.



Gold

Die Untersuchung von Semantiken für Petrinetze, die das Ein-/Ausgabeverhalten beschreiben, wurde fortgesetzt. Die Semantiken wurden zum Beweis der Korrektheit einer Petrinetzmodellierung eines Kommunikationsprotokolls verwendet. Ausserdem wurde eine Spursemantik definiert, die das Verklemmungsverhalten beschreibt. Sie ist kompositional bzgl. Parallelkomposition mit asynchroner Kommunikation und vollständig abstrahierend bzgl. einer Basissemantik, die für jede Eingabe angibt, ob das Netz eine Verklemmungsmöglichkeit besitzt.



Hernández, Brandmair, Kobler

Visualisierung und Animation analogischer Wissensstrukturen. Unter Animation versteht man die Darstellung von Programmverläufen durch geeignete Visualisierung von Datenstrukturen. Es wurde ein System entwickelt, das interne analogische Wissensstrukturen visualisiert und längerfristig auch eine Visualisierung von Ausbreitungs-algorithmen (constraint propagation) ermöglichen soll.



Kiehn

Es wurden Beweissysteme für semantische Äquivalenzen für Milners CCS untersucht. Durch Verallgemeinerung einer Beweismethode, die bisher nur für eine eingeschränkte Prozeßmenge anwendbar war, wurden Beweissysteme für Äquivalenzen mit expliziter Behandlung von Nebenläufigkeit entwickelt. Entgegen bisheriger Systeme kommen diese ohne ein erweitertes Aktionskonzept aus.



Kunde

Das von der DFG unterstützte Forschungprojekt "Entwurf und Analyse von grundlegenden Algorithmen für Prozessornetzwerke" (DFG-Projekt Ku 658/3 ) wurde vorläufig abgeschlossen.
Die Ergebnisse der Untersuchungen zum Vergleich unterschiedlicher Routingstrategien sind in einem Abschlußbericht und einer Dissertation niedergelegt.
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.
Weiterhin wurde mit der Untersuchung von Modellen zur Lastbalancierung begonnen.
Für Ringe mit intelligenten Speichern konnten erste optimale Resultate erzielt werden.



Lange, Rossmanith

Es wurden Komplexitätsklassen untersucht, welchen PRAM's und Schaltnetze mit exponentieller Größe zugrundeliegen. Dabei wurden Verbindungen zu Klassen wie P, UP und NP gefunden. Die Mächtigkeit des Lesezugriffs scheint bei exponentieller Prozessoranzahl nicht die Mächtigkeit des Modells selbst zu beeinflussen.



Mader, Barnard

Verifikation paralleler Prozesse mit Hilfe des modalen u-Kalküls. Dabei standen insbesondere Model-Checking Verfahren, Prozessalgebren und Halbordnungssemantik im Mittelpunkt.



Niedermeier, Rossmanith:

Die lokal definierten Akzeptanztypen von Uli Hertrampf wurden erweitert. In unserem neuen Modell lassen sich Komplexitätsklassen untersuchen, für welche dies bisher nicht möglich war. Dies betrifft vor allem eindeutige Klassen. Im Rahmen dieses Modells wurden Untersuchungen über verschiedene Arten des Orakelzugriffs auf eindeutige Komplexitätsklassen durchgeführt.



Schoett

Es konnte gezeigt werden, daß ein Programmodul genau dann mit Datenabstraktion verträglich ist, wenn alle seine abgeleiteten (Term-) Funktionen es sind. Folglich würde ein nicht-verträgliches Modul die erweiterte Church-Turing-These" von Tucker und Zucker widerlegen, die die berechenbaren Funktionen über gegebenen Basistypen und funktionen charakterisiert.
Es wurde gezeigt, daß bestimmte Typen im Lambda-Kalkül zweiter Stufe ausschließlich stabile Module beschreiben, wenn man sie im Modell der partiellen Äquivalenzrelationen (PERs) über den natürlichen Zahlen interpretiert. Noch offen ist, ob das Resultat auf partielle Algebren verallgemeinert werden kann.






3 Veröffentlichungen

Álvarez, C., Jenner, B.: A Note on Log Space Optimization, Technischer Bericht LSI-92-30-R, Dept. L.S.I, Universität Poltecnica de Catalunya, Barcelona, Dezember1992

Best, E., Cherkasova, L., Desel, J.: Compositional generation of home states in free choice systems - In: Formal Aspects of Computing Vol. 4, 1992, pp. 572 - 581

Boudol, G., Castellani, I., Hennessy, M., Kiehn, A. : A Theory of Processes with Localities - In: Tagungsband der LICS '92

Brauer, W., Brauer, U.: Wissenschaftliche Herausforderungen für die Informatik: Änderungen von Forschungszielen und Denkgewohnheiten - In: Informatik cui bono? Hrsg.: W. Langenheder u.a., Berlin: Springer, 1992, pp.11-19 (Reihe Informatik Aktuell)

Buntrock, G., Damm, C., Hertrampf, U., Meinel, Ch.: Structure and importance of logspace MOD-classes. - In: Mathematical Systems Theory, 1992, pp.223-237.

Damm, C., Holzer, M., Lange, K.-J.: Parallel complexity of iterated morphisms and the arithmetic of small numbers - In: Proc. of the 17th Symposium on Mathematical Foundations of Computer Science, Prag, Aug. 24-28, 1992. Eds.: I.M. Havel et al. Berlin: Springer, 1992, S. 227-235. (Lect. notes in computer science; 629)

Damm, C., Holzer, M., Rossmanith,P.:Expressing Uniformity via Oracles - In: Proceedings of the 7th International Meeting of Young Computer Scientists 1992, Volume I, pp. 74--84

Damm, C., Krause, M., Meinel, Ch., Waack, S.: Counting Communication Complexity Classes. - In: Proc. of 9th Symposium on Theoretical Aspects of Computer Science, Paris, Feb. 13-15, 1992. Eds.: A Finkel et al. Berlin: Springer, 1992, pp. 281-292. (Lect. notes on computer sciences; 577)

Desel, J.: Struktur und Analyse von Free-Choice-Petrinetzen, Dissertation, Technische Universität München, Wiesbaden, Deutscher Universitäts Verlag, 1992, 210 S., 43 Abb., 2 Tab.

Desel, J.: A proof of the rank theorem for extended free choice nets - In: Proc. XII. International Conference of Applications and Theory of Petri Nets, Sheffield, Jun. 22-26, 1992, Eds.: K. Jensen, Berlin: Springer, 1992, pp. 134-153. (Lect. notes in computer science; 616)

Desel, J., Esparza, J. : Shortest paths in reachability graphs - In: Hildesheimer Informatik Berichte Nr . 22/92, Universität Hildesheim, Institut für Informatik, 1992

Desel, J., Best, E., Esparza, J.: Traps characterize home states in free choice Petri Nets - In: Theoretical Computer Science Vol.101,1992, pp.161-176.

Desel, J., Gomm, D.,Kindler, E., Paech, B., Walter, R.: Bausteine eines kompositionalen Beweiskalküls für netzmodellierte Systeme. SFB-Bericht Nr. 342/16/92 A, Juli 1992

Desel, J., Reisig, W.: The synthesis problem of Petri Nets. SFB-Bericht Nr. 342/20/92 A Technische Universität München, Institut für Informatik, 1992

Eldracher, M.: Classification of non-linear-separable real-wold-problems using delta-rule, perceptions and topologically distributed encoding. - In: Applied Computing: Technological Challenges of the 1990's. Proc. of the 1992 ACM/SIGAPP Symposium on Applied Computing, Kansas City, Mar 1-3. Eds.: H. Berghel et al. New York: ACM Press, 1992, pp.1098-1104.

Eldracher, M.,Hernández, D., and Kinder, M.: Concept of an integrated trajectory generation system. Forschungsberichte Künstliche Intelligenz FKI-171-92, Institut für Informatik, Technische Universität München, Nov. 1992.

Ehring, H., Grosse-Rhode, M., Heise, A.: Specification Techniques for Concurrent and Distributed Systems - In: Conference Proceedings of the 2nd Maghrebien Conference on Software Engeneering and Artificial Intelligence, Forschungsberichte der TU-Berlin

Gold, R.: Dataflow Semantics for Petri Nets. - In: Proc. of the 17th Symposium on Mathematical Foundations of Computer Science, Prag, Aug. 24-28, 1992. Eds.: I.M.Havel et al. Berlin: Springer, 1992, pp. 275 - 283. (Lect. notes in computer science; 629)

Gold, R., Vogler, W.: Quality criteria for partial order semantics of place/transition-nets. Fundamenta Informaticae 17(3), pp. 187-210, 1992

Hernández, D.: Diagrammatical aspects of qualitative representations of space. - In: Proc. of the 1992 AAAI Spring Symposium on Reasoning with Diagrammatic Representations, Stanford University, March 25-27, 1992, Eds.: N.H. Narayanan, 1992, pp.225-228.

Hernández, D.: Qualitative Representation of Spatial Knowledge, Dissertation, Fakultät für Informatik, Technische Universität München, Dec. 1992.

Hernández, D.; Kinder, M.; Zimmermann, K.; Brauer, W.: Standardannahmen bei der qualitativen Repräsentation räumlichen Wissens. Tech. Report FKI-165-92, Technische Universität München, März 1992.

Hollatz, J., Tresp, V.: Structuring Networks Using Uncertain Rule-Based Knowledge - In: Proceedings of the Conference: Neural Networks for Computing, Snowbird, Utah, 1992

Hollatz, J., Tresp, V.: A Rule-Based Network Architecture - In: Proceedings of ICANN 92, Brighton, pp. 757-761, 1992

Hollatz, J.: Supplementing Neural Network Learning With Rule-Based Knowledge - In: Proceedings of IJCNN 92, Beijing, Vol. III, pp. 595-600, 1992

Hollatz, J., Tresp, V.: Rule-Based Knowledge in Neural Computing by Structuring the Network Architecture - In: Proceedings of DAGM '92, Dresden, Germany, Springer, pp. 88-95, 1992

Kinder, M.; Brauer, W.: Classification of trajectories - extracting invariants with a neural network. Tech. Report FKI-168-92, Technische Universität München, 1992. To appear in: Neural Networks 6/93.

Kindler, E.: Invariants, Compositionality, and Substitution. SFB-Bericht Nr. 342/25/92 A, Nov. 1992

Kunde, M., Tensi, T.: Balanced strategies for routing on meshes. - In: Data structures and efficient algorithms. Final Report on the DGF Special Joint Initiative. Eds.: B. Monien u.a. Berlin: Springer, 1992, pp. 289-308. (Lect. notes in computer science; 594)

Lange, K.-J., Rossmanith, P. : The emptiness problem for intersections of regular languages. - In: Proc. of 17th Symposium on Mathematical Foundations of Computer Science, Prag, Aug. 24-28, 1992. Eds.: I.M. Havel et al. Springer, 1991, pp. 346-354, 1991. (Lect. notes in computer science; 629)

Lange, K.-J., Rossmanith, P. und Rytter W.: Parallel Recognition and Ranking of Context-Free Languages. - In: Proceedings of 17th International Symposium on Mathematical Foundations of Computer Science (MFCS'92), Springer. pp. 24-36, 1992. (Lect. notes in computerscience; 629)

Lange, K.-J., Schudy, M.: The complexity of the emptinessproblem of EOL systems - In: Lindenmayer Systems. Hrsg.: G. Rozenberg et al. Berlin: Springer, 1992, pp. 167-176.

Laußermair, T.: Hyperflächen-Annealing, Dissertation, Institut für Informatik, Technische Universität München, April 1992

Mader, A.: Tableau Recycling - In: Proc. Fourth Workshop on Computer Aided Verification, Jun. 29 - Jul.1, 1992

Niedermeier, R.; Rossmanith, P.: Unambiguous simulations of auxiliary pushdown automata and circuits. - In: Proc. of 1st Latin American Symposium on Theoretical Informatics, Sao Paulo, Apr. 6-10. Ed: I. Simon. Berlin: Springer, 1992, pp. 387-400. (Lect. notes in computer science; 583)

Reisig, W.: Combining Petri Nets and other formal methods - In: Proc. XII. International Conference of Applications and Theory of Petri Nets, Sheffield, Jun. 22-26, 1992, Eds.: K. Jensen. Berlin: Springer, 1992, pp. 24-44. (Lect. notes in computer science; 616)

Reisig, W., Desel, J.: The Synthesis Problem of Petri Nets, SFB - Bericht 342/20/92 A, 1992

Reisig, W.: Elements of a Temporal Logic Coping with Concurrency, SFB - Bericht 342/23/92 A, 1992

Reisig, W.: Report on the REX Workshop on Semantics, Foundations and Applications EATCS Bulletin Nr. 84

Rossmanith, P. , Rytter, W.: Observations on log(n) time parallel recognition of unambiguous cfl's. Information Processing Letters 44, pp. 267-272, 1992

Schoett, O.: Two impossibility theorems on behaviour specification of abstract data types. - In: Acta Informatica 29 (1992), pp. 595-621

Schürmann, B., Gawronska, D., Hollatz, J.: Learning Properties of Multi-Layer Perceptrons with and without feedback, CLNL Workshop, Berkley, Sept. 1991, Tagungsband: The MIT Press, Cambridge, Massachusetts, 1992

Schröder, H., Turner, G., Kunde, M.: Optimal Odd-Even Balancing on the Ring Task System. Dept. of EE and Computer Science of the University Newcastle, Technical Report EE9253, 11 S., 1992

Tensi, T.: Balancierte Routingverfahren auf Gittern. Dissertationn, Technische Universität München, 139 S.,1992

Vogler, W.: Asynchronous communtcation of Petri Nets and the refinement of transitions. - In: ICALP 92, Proc. of the 19th Int. Colloquium on Automata, Languages and Programming 1992, Wien, July 13-17. Hrsg.: W. Kuich. Berlin: Springer 1992, pp. 605-616 (Lect. notes computer science; 623)

Vogler, W.: Modular construction and partial order semantics of Petri Nets. Berlin: Springer, 1992, IX, 252 S., 133 Abb. (Lect. notes computer science; 625)

Vogler, W.: Partial words versus processes: a short comparison. - In: Advances in Petri Nets 1992. Hrsg.: G. Rozenberg. Berlin: Springer, 1992, pp. 292-303. (Lect. notes computer science; 609)

Weiß, G.: Collective learning and action coordination, Tech. Report FKI-166-92, Technische Universität München, April 1992.

Weiß, G.: Learning the goal relevance of actions in classifier systems. - In: Proceedings of the 10th European Conference on Artificial Intelligence, Wien, Aug. 3-7, 1992, Ed.: B. Neumann. Chechester: Wiley, S. 430-434.

Weiß, G.: Action selection and learning in multi-agent systems. Tech. Report FKI-170-92. Technische Universität München. Oktober 1992. (Erscheint in Proceedings of the Second International Conference on Simulation of Adaptive Behavior.)

Weiß, G.: Towards the synthesis of neural and evolutionary learning. Interner Bericht. Technische Universität München. Januar 1992. Erscheint in O. Omidvar & C. Wilson (Eds.), Progress in Neural Networks (Vol. 5, Chapter 5). Norwood, New Jersey: Ablex Publ. Corp.







4 Vorträge

Brauer Damm Desel Eldracher Gold Heise Hernández Holzer Jenner Kiehn Kinder Kindler Kunde Lange Mader Niedermeier Reisig Rossmanith Schoett Traub Vogler Weiß Zimmermann





5 Vorlesungen und Seminare

Barnard, Kiehn, Mader, Reisig Brauer Brauer, Eldracher, Weiß Brauer, Eldracher, Kinder, Weiß Brauer, Hernández, Weiß Brauer, Vogler, Gold Kunde Kunde, Lange, Holzer, Niedermeier, Rossmanith Lange Lange,Holzer, Niedermeier, Rossmanith Reisig Reisig, Gomm et al Rossmanith Taubner Vogler




6 Sonstige Tätigkeiten

Barnard Brauer Desel Eldracher Gold Gomm Heise Hernández Jenner Kiehn Kinder Kindler Kunde Lange Mader Niedermeier Reisig Rossmanith Schoett Vogler Walter Weiß Zimmermann




7 Forschungsberichte Künstliche Intelligenz

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
Arcisstraße 21
D - 8000 München 2

Tel.: +49 - 89 - 280 52 17
Telex: tumue d 05 - 22854
Fax: +49 - 89 - 2105 - 8207
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:

Login: anonymous
Maschine: flop.informatik.tu-muenchen.de (131.159.8.35)
Verzeichnis: pub/fki






8 Rufnummern/E-Mail-Adressen

Name Tel.-Nr. E-Mail-Anschrift
Barnard, D. 2105-2391 barnard@informatik.tu-muenchen.de
Biberger-Karl, I. (Sekretariat) 2105-2404 bibergei@informatik.tu-muenchen.de
Brauer, W. 2105-2401 brauer@informatik.tu-muenchen.de
Desel, J. 2105-2395 desel@informatik.tu-muenchen.de
Eldracher, M. 2105-2406 eldrache@informatik.tu-muenchen.de
Freksa, C. 2105-2606 freksa@informatik.tu-muenchen.de
Gold, R. 2105-2387 gold@informatik.tu-muenchen.de
Gomm, D. 2105-8237 gomm@informatik.tu-muenchen.de
Grylka, P. (Sekretariat) 2105-2402 grylka@informatik.tu-muenchen.de
Heise, A. 2105-2387 heise@informatik.tu-muenchen.de
Hernández, D. 2105-2606 danher@informatik.tu-muenchen.de
Holzer, M. 2105-2407 holzer@informatik.tu-muenchen.de
Kiehn, A. 2105-2388 kiehn@informatik.tu-muenchen.de
Kinder, M. 2105-2406 kinder@informatik.tu-muenchen.de
Kindler, E. 2105-2391 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-8237 mader@informatik.tu-muenchen.de
Niedermeier, R. 2105-2397 niederme@informatik.tu-muenchen.de
Reisig, W. 2105-2405 reisig@informatik.tu-muenchen.de
Rossmanith, P. 2105-2397 rossmani@informatik.tu-muenchen.de
Schoett, O. 2105-2399 schoett@informatik.tu-muenchen.de
Weiß, G. 2105-2406 weissg@informatik.tu-muenchen.de
Zimmermann, K. 2105-2406 zimmerma@informatik.tu-muenchen.de
Systemadministration 2805217 root@flop.informatik.tu-muenchen.de
Rechnerraum 2805218 root@flop.informatik.tu-muenchen.de



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