[Donnerstag] Forschungskolloquien
Torsten Schaub
torsten at cs.uni-potsdam.de
Mon Oct 18 07:15:04 CEST 1999
Guten Tag!
mo"chte Sie hiermit ganz herzlich zum Vortrag im Rahmen des
Institutskolloquiums am Donnerstag 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.
__________________________________________________________________
More information about the Fsr-inf-fachschaft
mailing list