[ Próxima Página | Página Anterior | Página Principal ]
Teoria dos Modelos surgiu na lógica clássica, que, pode-se dizer,
se propunha a resolver os paradoxos da infinitude, e elucidar a natureza do
infinito. As principais construções da Teoria dos Modelos
produzem estruturas infinitas, e os métodos assumem que as estruturas
são, em geral, infinitas. Entretanto, muitas estruturas de interesse em
Ciência da Computação são finitas. Daí, o
interesse em Teoria dos Modelos Finitos ter nascido justamente de
questões provenientes da Teoria da Computaçáo (em
particular, teoria de banco de dados, e teoria da complexidade). Nota-se,
porém, que a maior
parte dos resultados e métodos sobre os quais está montada a
Teoria dos Modelos falha quando nos restringimos a estruturas finitas. Por
exemplo, o Teorema da Compaccidade.
O uso das técnicas da Teoria dos Modelos Finitos para estudar
as classes de complexidade de algoritmos deu origem ao que se chama de
Complexidade Descritiva. Enquanto que na Teoria da Complexidade
Computacional estuda-se a complexidade de problemas em função de
um modelo de máquina de computação baseado em
strings, e mede-se a complexidade de uma linguagem através dos
recursos necessários (tempo, espaco, etc.) para decidir a
pertinência de um determinado string a uma classe de strings, em
Complexidade Descritiva procura-se estudar a complexidade da
descrição, usando uma linguagem lógica,
de uma determinada coleção de estruturas quaisquer.
Dr Anuj Dawar, do Department of Computer Science, University of Wales Swansea,
UK, especialista em Complexidade Descritiva, e organizador do encontro
Finite Model Theory - Problems, Methods and Applications. A Tutorial, Swansea, UK,
7 a 9 de Julho de 1996,
apresentou as seguintes
palestras:
7 de Agosto, 09:30-11:30
Tutorial on Finite Model Theory and Complexity Theory
9 de Agosto, 09:00-10:00
Descriptive Polynomial Time Complexity (slides here)
12 de Agosto, 09:00-10:00
Finite Variable Logics on Finite Structure (slides here)
13 de Agosto, 09:00-10:00
Capturing Complexity Classes with Generalized Quantifiers (slides here)
Material sobre as apresentações de Anuj Dawar (sob forma de
arquivos postscript contendo as transparências das aulas proferidas)
está disponível na Internet através do
endereço http://www.di.ufpe.br/~ruy/dawar.
(Ver também http://www.swan.ac.uk/compsci/EventsFolder/FMT.html).