**Subject: **Nov 18: G.Gottlob, Existential 2nd Order Logic over Strings

**From: **Helmut Veith (*kgs-owner@dbai.tuwien.ac.at*)

**Date: **Thu Dec 11 1997 - 22:00:25 MET

**sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Next message:**Kurt Gödel Society: "Newsletter 97"**Previous message:**Helmut Veith : "Nov 27-28: Shport Course on Probabilistic Proofs"

Lecture Announcement

-------------------------

Georg Gottlob

=================================================

Vienna University of Technology

Existential Second Order Logic over Strings

-------------------------------------------

Thursday, December 18, 16:45

ABSTRACT:

Existential second order logic (ESO) and monadic second order logic

(MSO) have attracted much interest in logic and computer science.

ESO is a much more expressive logic over word structures than

MSO. However, little was known about the relationship between

syntactic fragments of ESO and MSO. We shed light on this issue by

completely characterizing this relationship for the prefix classes of

ESO over strings (i.e., finite word structures). Moreover, we

determine the complexity of model checking over strings, for all

ESO-prefix classes. Let ESO(Q) denote the ESO prefix class with

first-order quantifier prefix from prefix set Q. We show that

ESO(E*AE*)=ESO(Ackermann) and ESO(E*AA) are the maximal standard

ESO-prefix classes contained in MSO, thus expressing only regular

languages. We further prove the following dichotomy theorem:

an ESO prefix-class either expresses only regular languages

(and is thus semantically contained in MSO), or it expresses

some NP-complete languages. We also give a precise characterization

of those ESO-prefix classes which are equivalent to MSO over strings,

and of the ESO-prefix classes which are closed under complement on strings.

(Joint work with Th. Eiter and Y. Gurevich)

PLACE:

Seminarraum SEM 181A, Institut fuer Informationssysteme,

Paniglgasse 16, 1. Stock, 1040 Wien.

------------------------

Kurt-Goedel-Gesellschaft

Technische Universitaet Wien

Institut fuer Computersprachen E185.2

Resselgasse 3/1, A-1040 Wien

Tel: (+43 1) 588 01/4088

Fax: (+43 1) 504 15 89

email: mailto:kgs@logic.tuwien.ac.at

http://logic.tuwien.ac.at:80/kgs/home.html

listserver: mailto:listproc@dbai.tuwien.ac.at

Mit Unterstuetzung des

Bundesministeriums fuer Wissenschaft und Forschung

**Next message:**Kurt Gödel Society: "Newsletter 97"**Previous message:**Helmut Veith : "Nov 27-28: Shport Course on Probabilistic Proofs"

*
This archive was generated by hypermail 2b25
: Thu Apr 06 2000 - 16:19:18 MET DST
*