[Doc2010] Defesa de Proposta de Tese de Doutorado

[Manoel Orley]

Convidadamos a todos assistirem a uma Defesa de Proposta de Tese de Doutorado, como segue:

Aluno: Francicleber Martins Ferreira
Título: Expressividade e Complexidade em Lógicas Preferenciais,
Híbridas e de Grau Limitado

Banca: Profa. Dra. Ana Teresa Martins (Orientadora DC/UFC)
        Prof. Dr. Carlos Brito (DC/UFC)
        Prof.Dr. Edward Hermann Hauesler(PUC/RJ)
        Prof.Dr. João Fernando Alcântara (DC/UFC)
        Prof.Dr. Mario Roberto Benevides (UFRJ)

Local: Sala de Vídeo Conferência do GREAT - Bloco 942-A
Data/hora: 26 de outubro as 13:00h

Resumo: Nós investigamos a expressividade de lógicas cuja semântica
difere das semânticas estudadas em teoria dos modelos clássica por
apresentar relações entre modelos ou por restringir a classe dos
modelos a modelos finitos.

Nós estudamos a expressividade de lógicas preferenciais,que apresentam
relações de preferencia entre modelos, utilizando a abordagem da
Teoria dos Modelos Abstrata. Nessa abordagem, estudamos a semântica de
classes de lógicas através das propriedades da relação de
satisfatibilidade sem necessariamente explicitar a estrutura da
linguagem. Nós mostramos que, para um conjunto de lógicas
preferenciais, a classe dos modelos minimais de um conjunto finito de
formulas pode ser axiomatizado na lógica subjacente sem se considerar
a relação de preferencia se, e somente se, puder ser finitamente
axiomatizado. Aplicamos esse resultado para estudar questões de
definibilidade.

Estudamos também a expressividade de lógicas modais híbridas sobre
modelos finitos. Nós mostramos que propriedade de grafos na Hierarquia
Polinomial podem ser expressas por fórmulas da lógica hibrida
completa, com respeito a definibilidade de "frames", através de
fórmulas de tamanho polinomial em função da cardinalidade dos grafos.
Nós mostramos que o mesmo vale para o fragmento da lógica híbrida sem
as modalidades globais se restringirmos os modelos a grafos conexos e
com "loops". Desses resultados obtemos uma prova alternativa da
NP-dificuldade do problema de model-checking de um fragmento
específico da logica hibrida.

Na última parte desse trabalho, investigamos o fragmento da lógica de
segunda-ordem onde apenas relações de grau limitado são quantificadas.
Utilizando resultados de Grandjean, Olive e Schwentick, mostramos que
esse fragmento captura a classe ALIN dos problemas sobre estruturas
unárias que podem ser resolvidos por uma máquina de registradores
não-determinística alternante em tempo linear. Nós estudamos a
extensão dessa lógica obtida ao adicionarmos o operador de fecho
transitivo e relacionamos sua expressividade com classes de
complexidade de espaço limitado.

Atenciosamente,
Orley
  

-- 
Manoel Orley Mendes Carneiro
Mestrado e Doutorado em Ciência da Computação
Universidade Federal do Ceará
Telefones:55 85 3366-9847 (Ext-216) e 9997-4809