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

Subject: Nov 18: G.Gottlob, Existential 2nd Order Logic over Strings
From: Helmut Veith (
Date: Thu Dec 11 1997 - 22:00:25 MET

Lecture Announcement

Georg Gottlob
Vienna University of Technology

Existential Second Order Logic over Strings
Thursday, December 18, 16:45


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)


Seminarraum SEM 181A, Institut fuer Informationssysteme,
Paniglgasse 16, 1. Stock, 1040 Wien.

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

Mit Unterstuetzung des
Bundesministeriums fuer Wissenschaft und Forschung

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