[HEUTE] Forschungskolloquien

[Torsten Schaub]

Guten Tag!

ich mo"chte Sie hiermit ganz herzlich zum heutigen Vortrag im Rahmen des
Institutskolloquiums einladen.

Weitere Details entnehmen Sie bitte der beigef"ugten
Ank"undigung oder unseren WWW-Seiten unter:

 http://www.cs.uni-potsdam.de/inst_koll/index.html


 Mit freundlichen Gru"ssen, -torsten schaub

     __________________________________________________________________
   
                       Forschungs-Kolloquium: 21. Oktober
                                        
   am Institut für Informatik der Universität Potsdam
   
                                      -
                                      
   Der Vortrag findet am 21. Oktober 1999 um 15.30 Uhr
   in Raum 0.57, Haus 22, Campus Am Neuen Palais statt.
   
Titel

   Über Beweiskomplexität Nichtmonotoner Logiken
   
Referent

   Dr Hans Tompits, TU Wien
   
Resümee

   Systeme nichtmonotonen Schließens wurden Anfang der 80er Jahre als
   Mittel zur Repräsentation unvollständigen Wissens eingeführt. Eine der
   grundlegenden Ideen dieser Methoden war, daß mit Hilfe nichtmonotoner
   Regeln die Effizienz von AI-Systemen gesteigert werden sollte. Es
   stellte sich allerdings bald heraus, daß diese Hoffnung nicht ganz
   erfüllt wurde, da nichtmonotone Logiken im Allgemeinen eine höhere
   Berechnungskomplexität aufweisen als klassische Logik.
   
   In diesem Vortrag werden wir den Einfluß nichtmonotoner Regeln auf die
   minimale Beweislänge in schnittfreien Sequenzensystemen erster Stufe
   betrachten. Es zeigt sich, daß für bestimmte Klassen
   prädikatenlogischer Formeln die Anwendung nichtmonotoner Regeln sehr
   wohl zu einer Vereinfachung des Systemverhaltens führen kann, und zwar
   gilt für diese Formeln, daß die minimale Beweislänge ohne nichtmonotone
   Regeln nicht-elementar länger ist als die minimale Beweislänge mit
   Anwendungen nichtmonotoner Regeln. Der Grund für dieses Verhalten liegt
   darin, daß die nichtmonotonen Regeln gewisse Instanzen der analytischen
   Schnittregel simulieren können. Als Basis unserer Analyse werden zwei
   der wichtigsten nichtmonotonen Formalismen verwendet, nämlich Default
   Logik und Circumscription.
     __________________________________________________________________