Campus Event Calendar
Event Entry
New for: D1, D2
What and Who
Computational Model Theory
Moshe Vardi
MPI-Kolloquium
AG 1, AG 2
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 27 October 97
16:15
-- Not specified --
46.1
019
Saarbrücken
Abstract
Model theory and recursion theory are two distinct and quite
separate branches in mathematical logic. On the other hand,
finite-model theory and complexity theory, which constitute
their analogues in computer science, are intimately interrelated,
giving together rise to computational model theory. Underlying
this theory is the extension of first-order logic with iteration
constructs, in order to make the logic ``computational''.
These iterative logics can be viewed as effective fragments of
infinitary finite-variable logic, whose expressive power can
be captured by means of pebble games. Alternatively, these
logics can be viewed as complexity-bounded classes of relational
machines, which are Turing machines equiped with a relational
store. Thus, characterizing the expressive power of these logics
is equivalent to understanding the relationship between complexity
classes such as PTIME and PSPACE.
separate branches in mathematical logic. On the other hand,
finite-model theory and complexity theory, which constitute
their analogues in computer science, are intimately interrelated,
giving together rise to computational model theory. Underlying
this theory is the extension of first-order logic with iteration
constructs, in order to make the logic ``computational''.
These iterative logics can be viewed as effective fragments of
infinitary finite-variable logic, whose expressive power can
be captured by means of pebble games. Alternatively, these
logics can be viewed as complexity-bounded classes of relational
machines, which are Turing machines equiped with a relational
store. Thus, characterizing the expressive power of these logics
is equivalent to understanding the relationship between complexity
classes such as PTIME and PSPACE.
In this expository talk the speaker will survey 15 years of research
in this area.
Contact
Uwe Waldmann
(0681) 9325-227
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Alle Interessenten sind herzlich zum Vortrag und zum Kaffee und Tee
(ab 13.45 Uhr im Gebaeude 46.1, 1. Etage) eingeladen.
--
Uwe Waldmann, Max-Planck-Institut fuer Informatik (Arbeitsgruppe Ganzinger)
Geb. 46.1, Raum 627
Tel.: uni-intern 92227/92299(FAX), sonst (0681) 9325-227/-299(FAX),
Uwe Brahm, 04/12/2007 12:44 -- Created document.