Pesquisa e Pós-Graduação em
Ciência da Computação

ÁREA DE TEORIA DA COMPUTAÇÃO

Subárea: Teoria dos Modelos

De que se trata?

Teoria dos Modelos estuda 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 estão sobretudo:
1. que propriedades podem ou não podem ser expressas em uma certa linguagem?
2. que estruturas ou relações podem ou não podem ser definidas em uma certa linguagem?

Modelos Finitos e Complexidade Descritiva

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, espaço, 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. Tal linha de pesquisa tem demonstrado bastante vigor e aceitação, e tem contribuido para resolver problemas em teoria da complexidade que há muito tempo estavam em aberto, tais como:
(1) For all s(n) greater than or equal to log n, nondeterministic space s(n) is closed under complementation. (Ver página do autor do resultado: Neil Immerman)
(2) A questão "existe uma linguagem de consulta que possa expressar exatamente as polynomial time generic queries em um banco de dados relacional?" proposta por A. Chandra & David Harel (1982), foi parcialmente respondida em 1995, com repercussões em teoria da complexidade, por Serge Abiteboul e Victor Vianu (General Chairman do simpósio Principles of Database Systems - PODS'99): "Inflationary Fixpoint Logic" and "Partial Fixpoint Logic" have the same expressive power if, and only if, the complexity classes PTIME and PSPACE co-incide.

Uma vez estabelecido que a lógica de primeira ordem não é apropriada para formalizar classes de estruturas finitas, a procura por lógicas que pudessem descrever exatamente a classe de estruturas finitas em classes de complexidade específicas (LOGSPACE, NLOGSPACE, PSPACE, PTIME, etc.) foi desempenhada vigorosamente no início dos anos 80 por N. Immerman (1986) and M. Vardi (1982) que demonstraram, por exemplo, que existem extensões `naturais' da lógica de primeira ordem (i.e. as chamadas `lógicas de ponto fixo', que resultam da adição à lógica de primeira ordem de um operador para indução monotônica relacional) que caracterizam PTIME sobre estruturas ordenadas.

A questão fundamental sobre a possibilidade de se encontrar `casamentos' semelhantes (lógicas versus classes de complexidade) no caso mais geral de estruturas não necessariamente ordenadas continua em aberto. A ferramenta chamada `jogos semânticos', desenvolvida para estabelecer o poder expressivo da lógica de primeira ordem, tem sido bastante útil na resolução da questão para algumas classes particulares de estruturas. Os resultados têm se mostrado relevantes em aplicações na área de linguagens de consulta a bancos de dados relacionais.

Parece haver um pressentimento entre pesquisadores em teoria de modelos finitos que as técnicas usadas correntemente se tornaram muito limitadas, e talvez seja tempo de se buscar alguns dos recentes recursos em teoria de modelos, em particular, estabilidade e/ou simplicidade, ferramentas suficientemente fortes para permitir uma abertura de novas perspectivas. Transcrevemos de Dawar et al. (1998) ("Ordering finite variable types with generalized quantifiers". In Proc. 13th annual IEEE symposium on logic in computer science - LICS'98):

Teoria da Estabilidade

Atualmente uma das subáreas mais ativas da Teoria dos Modelos, a Teoria da Estabilidade concerne a classificação de estruturas matemáticas através dos objetos combinatórios que podem ser nelas definidos.
Nascida no início dos anos 1960s com o Teorema da Categoricidade de M. Morley, e desenvolvida no programa de pesquisa originalmente concebido por Saharon Shelah (i.e. "a contagem do número de modelos não-isomorfos de uma determinada teoria de primeira ordem"), até o início dos anos 1980s o foco de atenção da Teoria da Estabilidade estava no trabalho de Shelah que consistia basicamente da busca de uma demonstração de uma conjectura de Morley ("a função de espectro de uma teoria de primeira ordem contável completa T é não-decrescente sobre cardinais incontáveis"). A demonstração de Shelah foi construída ao longo de quase 15 anos e é o principal tópico de seu enorme tratado sobre Classification theory. O tema predominante no livro de Shelah concerne a busca de subconjuntos de um modelo de uma teoria estável sobre o qual a dependência bifurcante é suficientemente boa a ponto de admitir uma teoria de dimensão.
A Teoria Geométrica da Estabilidade (concebida por Ehud Hrushovski em 1987) estuda a estrutura fina de modelos de teorias estáveis. Um tema sempre presente é a existência e a estrutura de grupos definíveis. Uma exposição profunda da teoria e de suas aplicações fundamentais à teoria da classificação foi realizada por Anand Pillay em seu livro Geometric Stability Theory (1996). Nos últimos anos têm-se observado o surpreendente sucesso da aplicação da teoria a várias outras áreas da matemática, tal como, por exemplo, geometria diofantina.
As principais ferramentas utilizadas na Teoria Geométrica da Estabilidade são, essencialmente: geometrias, ortogonalidade, modularidade, grupos estáveis.
Recentes desenvolvimentos, sobretudo a partir de um artigo do próprio Shelah ("Simple unstable theories", Ann. of Math. Logic 19(1980):177-203), fornecem um ferramental bastante útil para o estudo de modelos finitos, principalmente o conceito de "teorias simples" (grosso modo, as teorias nas quais não se pode definir ordem parcial com uma cadeia infinita), permitindo inclusive a simplificação de algumas das construções originalmente desenvolvidas por Shelah (ver recente survey "From Stability to Simplicity", de B. Kim e A. Pillay, Bulletin of Symbolic Logic 4(1998):17-36, e o livro de F. Wagner: Simple Theories, Kluwer, 2000, ISBN: 0-7923-6221-7).

Teses e Dissertações Concluídas

Doutorado

  • Complexidade Descritiva de Problemas em Grafos
       Haroldo G. Benatti
       Março de 2000.

    Teses e Dissertações em Andamento

    Doutorado

  • Contributions to the investigations of Lascar strong types in simple theories
       Steffen Lewitzka
       Término: Abril de 2003.

    Última atualização: 29 de Dezembro de 2004, 10:17:06 GMT-0300.