Lógica, Provas e Algoritmos

[ Próxima Página | Página Anterior | Página Principal ]



Anuj Dawar: Finite Model Theory and Complexity Theory

Teoria dos Modelos investiga a relação entre estruturas (matemáticas) e linguagens (formais). Um dos seus principais objetivos é determinar os limites de definibilidade de certas linguagens formais. Dentre as questões que a Teoria dos Modelos procura responder destacam-se:

  • que propriedades podem ou não podem ser expressas em uma certa linguagem?

  • que estruturas ou relações podem ou não podem ser definidas em uma certa linguagem?

    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).