Complexidade Descritiva de Problemas em Grafos
por
Haroldo Gonçalves Benatti

Tese apresentada ao Departamento de Informática da Universidade Federal de Pernambuco para Obtenção do Grau de Doutor em Ciência da Computação

Data da Defesa: 24 de Março de 2000

Banca Examinadora: Kátia Silva Guimarães (CIn-UFPE), José Dias dos Santos (CIn-UFPE), Marcelo Finger (DCC/IME-USP), Jayme L. Szwarcfiter (COPPE-UFRJ).

Orientador: Ruy J. G. B. de Queiroz

(Durante a elaboração deste trabalho, o autor recebeu apoio financeiro da CAPES)

(Para obter o arquivo postscript com o texto integral clique aqui)

Resumo

Neste trabalho analisamos diversas questões referentes à definibilidade de diversos problemas de grafos em linguagens formais que são extensões da lógica de primeira ordem.

Com este objetivo em mente, analisamos a expressividade da lógica de primeira ordem, de suas extensões através de operadores de ponto fixo e de algumas lógicas infinitárias, buscando sempre estabelecer relações com classes de complexidade computacional. Dedicamos atenção especial aos jogos no estilo de Ehrenfeucht por serem uma ferramenta importante para a obtenção de resultados de expressividade em diversas das lógicas estudadas.

Usamos jogos deste tipo para mostrar que diversos problemas de modularidade de caminhos e circuitos em grafos orientados finitos não são definíveis no segmento existencial livre de negação da lógica infinitária com um número finito de variáveis. Procedemos também este estudo quando restringimos a entrada destes problemas a grafos orientados bipartidos. Em seguida, mostramos que o problema da existência de dois caminhos disjuntos entre dois pares de vértices dados em grafos não-orientados finitos é definível na lógica obtida pelo acréscimo do operador de menor ponto fixo à lógica de primeira ordem. Obtemos também, um resultado parcial para a definibilidade deste problema no segmento existencial livre de negação da lógica infinitária com um número finito de variáveis.

Os resultados mencionados no último parágrafo não foram encontrados na literatura. Estes resultados constituem uma espécie de complexidade descritiva "concreta" e a realização de estudos nesta linha são de bastante importância para áreas como Banco de Dados. Por fim, discutimos diversas possibilidades para a continuação deste trabalho.

Publicações

Benatti, H. & de Queiroz, R.: 2006, `On the Descriptive Complexity of the Two Disjoint Paths Problem Over Undirected Graphs'. Bulletin of the Section of Logic (ISSN 0138-0680), Volume 35, Number 4, pp. 195-214, 2006.

Benatti, H. & de Queiroz, R.: 2005, `Descriptive Complexity of Modularity Problems on Graphs'. Bulletin of the Section of Logic (ISSN 0138-0680), Volume 34, Number 2, pp. 61-76, 2005.

Última atualização: 28 de Junho de 2007, 11:29am GMT-0300.