Título: Aprendizagem de Fórmulas da Lógica de Primeira-Ordem sobre Classes de Estruturas Relacionais

Data: 15/12/2017 Horário: 14h Local: Sala de Seminários

Resumo:

Nós investigamos o seguinte problema para uma classe de estruturas relacionais fixada C: dado dois conjuntos finitos P e N de estruturas em C, encontrar uma fórmula da lógica de primeira-ordem sobre C que seja satisfeita por toda estrutura em P e por nenhuma em N. Nós usamos uma medida de similaridade entre estruturas definida pelos jogos Ehrenfeucht–Fraïsse. Nós consideramos as seguintes classes de estruturas: conjuntos, estruturas de relações unárias, ordens lineares, união disjunta de ordens lineares, estruturas de equivalência e estruturas de palavras. Os algoritmos de aprendizagem definidos para essas classes de estruturas executam em tempo polinomial no tamanho da entrada.

Banca:

• Profª. Drª. Ana Teresa de Castro Martins (MDCC/UFC - Orientador)
• Prof. Dr. Francicleber Martins Ferreira (UFC - Coorientador)
• Prof. Dr. João Fernando Lima Alcântara (MDCC/UFC)
• Prof. Dr. Ruy José Guerra Barretto de Queiroz (UFPE)