20.6.: Logic and Complexity Lectures

From: Helmut Veith (kgs-owner@dbai.tuwien.ac.at)
Date: Mon Jun 17 2002 - 18:52:57 MEST

  • Next message: Helmut Veith: "26.6.: H. Ganzinger, Integration von Entscheidungsverfahren in"

    Thursday, June 20, 4 pm - 6 pm

    Markus Frick, University of Edinburgh
    ==================================================
    Die parametrische Komplexitaet von Model-Checking

    Miki Hermann, Ecole Polytechnique, Palaiseau
    (joint work with Arnaud Durand)
    =====================================================
    The Inference Problem for Propositional Circumscription
    of Affine Formulas is coNP-complete

    PLACE: TU Wien, Abteilung für Wissensbasierte Systeme
    Seminarraum 184/3, 3ter Stock, Favoritenstr. 11

    Abstract Frick: Das Model-Checking Problem sieht wie folgt aus: gegeben:
    eine Eigenschaft q formuliert in einer Sprache L und eine Struktur A aus
    einer Klasse C gesucht: gilt q in A ? Unsere Aufmerksamkeit gilt dabei
    besonders der parametrischen Komplexitaet dieser Probleme. Wir fragen
    also, ob es einen Algorithmus gibt der dieses Problem in Zeit f(||q||)
    p(||A||) fuer ein Polynom p entscheidet. Wir beschraenken uns dabei auf
    die Logiken der ersten Stufe und der monadischen zweiten Stufe. Der
    Vortrag hat Uebersichtscharakter und bietet eine Uebersicht ueber das
    Gebiet des Model-Checking. Wir zeigen, wie sich algorithmische Problem in
    diesen Sprachen formalisieren lassen und welche Komplexitaet wir zu
    erwarten haben. Insbesondere gehen wir dabei auf eine Reihe neuerer
    Arbeiten und Ergebnisse auf diesem Gebiet ein.

    Abstract Hermann: We prove that the inference problem of propositional
    circumscription for affine formulas is coNP-complete, settling this way an
    open question in the complexity analysis of this problem. We also show
    that the considered problem becomes polynomial-time decidable if only a
    single literal has to be inferred from an affine formula. Our
    intractability result has also a relation to other complexity results in
    coding theory.



    This archive was generated by hypermail 2b30 : Mon Jun 17 2002 - 18:54:33 MEST