January 21: B. Loescher, Existentially quantified function variables


Subject: January 21: B. Loescher, Existentially quantified function variables
From: Helmut Veith (kgs-owner@dbai.tuwien.ac.at)
Date: Mon Jan 18 1999 - 09:49:47 MET


Lecture Announcement
-------------------------

Bernd Loescher
=================================================
Vienna University of Technology

EXISTENTIALLY QUANTIFIED FUNCTION VARIABLES
------------------------------------------
Thursday, January 21, 16:30 - 18:30

GERMAN ABSTRACT:

EXISTENTIELL QUANTIFIZIERTE FUNKTIONSVARIABLEN

Dieser Vortrag stellt mein am Institut fuer Informationssysteme (TU Wien)
durchzufuehrendes Forschungsprojekt vor. Dieses Projekt wird vom TMR
Programm der Europaeischen Union finanziert.

Seit Fagins Resultat, dass existentielle Logik zweiter Ordnung die Klasse
NP charakterisiert, sind viele Anstrengungen zur Untersuchung der
Feinstruktur dieser Logik unternommen worden. Ueblicherweise werden hier
relationale Fragmente betrachtet (zum Beispiel monadische existentielle
Logik zweiter Ordnung, in der nur ueber unaere Relationsvariablen
quantifiziert werden kann).

In diesem Vortrag betrachten wir funktionale Fragmente, und insbesondere
das Fragment mit ausschliesslich unaeren quantifizierten
Funktionsvariablen. Solche Klassen sind von Bedeutung, weil 1) sie die
Klasse NLIN (nicht-deterministische lineare Zeit) charakterisieren
koennen, 2) neue Methoden vorhanden sind, die genau hier passend sind, und
3) Folgerungen fuer relationale Fragmente von der Analyse der funktionalen
Fragmente abgeleitet werden koennen.

Wir betrachten die Hierarchie, die auf der Zahl der quantifizierten
unaeren Funktionsvariablen basiert. Wir zeigen ihre Echtheit auf der
untersten Stufe und geben Gruende fuer die Vermutung an, dass auch die
weiteren Stufen echt sind, sowie Konsequenzen. Wir praesentieren dafuer
als Werkzeuge die quadratischen Gitter, endliche Automaten, die auf
solchen Gittern arbeiten, sowie Henkin Quantoren an, von denen neue
Ergebnisse erwartet werden koennen.

ENGLISH ABSTRACT:

EXISTENTIALLY QUANTIFIED FUNCTION VARIABLES

This talk presents my research project to be undertaken at the Institut
fuer Informationssysteme (TU Wien). This project is funded by the TMR
program of the European Union.

Since Fagin's result that existential second order logic characterises NP,
much work has been undertaken to analyse the fine structure of this logic.
Usually, relational fragments are considered (for example, monadic
existential second order logic, where only unary relation variables may be
quantified).

In our talk, we consider functional fragments, and especially the fragment
with only unary function variables to be quantified. Such classes are of
interest because 1) they can characterise the class NLIN
(non-deterministic linear time), 2) new methods fitting especially those
fragments are available, and 3) implications on the relational
fragments can be derived from the analyse of the functional fragments.

We consider the hierarchy based on the number of quantified unary function
variables. We show the strictness on the lowest level, and give
some evidence for the rest of this hierarchy to be strict, as well as some
implications. We present the tools of square grids, finite automata
working on these, and Henkin quantifiers, from which new results may be
expected.

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

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



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