Título: Complexidade Descritiva de Lógicas de Ponto Fixo Relacionais.

Data: 06/11/2015 Horário: 10h Local: Sala de Seminários - Bloco 952 - Campus do Pici

Resumo:

Complexidade Descritiva é um ramo da Teoria dos Modelos Finitos que está interessada em caracterizar classes de complexidade computacionais em termos dos recursos lógicos necessários para expressar todos os problemas que estão contidos na classe. O resultado mais celebrado da área é o Teorema de Fagin que prova que a classe NPTIME é capturada pelo fragmento existencial de segunda ordem, e teve o fato que a lógica de primeira ordem não é expressiva o suficiente para definir problemas simples como o problema da conectividade de grafos. A introdução de operadores de ponto fixo é uma técnica padrão para acrescentar poder expressivo à lógica de maneira controlada. De fato, em Immerman e Vardi é provado que a lógica de primeira ordem com o operador de menor ponto fixo, denotada por LFP, é capaz de capturar a classe PTIME sobre estruturas ordenadas. Nosso trabalho é comparável ao trabalho descrito em Abtiboul et. all, o qual introduz a noção do ponto fixo não-determinístico e prova que a lógica de primeira ordem com tal operador captura a classe NPTIME. Neste trabalho, seguiremos uma abordagem diferente e definiremos a noção de ponto fixo sobre uma relação R arbitrária. A ideia básica é que X é um ponto fixo da relação R no caso em que o par (X,X) está na relação R. Introduziremos a noção do ponto fixo indutivo inflacionário de uma relação R e associaremos o operador rifp. Denotaremos por RIFP_1 o fragmento da lógica de primeira ordem com o operador de ponto fixo relacional inflacionário rifp, com a restrição que este operador é aplicado no máximo uma vez, como elemento mais externo à fórmula. Como resultado segue que a lógica RIFP_1 captura a classe NPTIME. Outro resultado que descreveremos é que a lógica RIFP = PH. Concluíremos esse resultado mostrando que toda fórmula em RIFP possui uma fórmula equivalente em lógica de segunda ordem (SO).

Banca:

• Profª. Drª. Ana Teresa de Castro Martins (MDCC/UFC - Orientadora)
• Dr. Francicléber Martins Ferreira (MDCC/UFC)
• Prof. Dr. João Fernando Lima Alcântara (MDCC/UFC)
• Prof. Dr. Edward Hermann Haeusler (PUC-RJ)