While performing information extraction or natural language processing tasks, one usually encounters problems when working with data or texts containing noise, typing mistakes or other different kinds of errors. In this thesis we investigate the use of modified Levenshtein edit distances to deal with these problems in two specific tasks. The first one is the record linkage in databases where distinct records can be representing the same entity. For this task we used and extended the WEKA API for Machine Learning and we were able to show that a modified Levenshtein distance provides good precision and recall results in the detection of records representing the same entities. The second task is the search and annotation of occurrences of specified words in texts written in natural language. Our main result in this task was the implementation of an approximate Gazetteer for GATE, the General Architecture for Text Engineering.

A Logica Modal tem sido utilizada em Ciencia da Computacao no tratamento de crencas, conhecimento, processamento de linguagem natural, analise de sistemas distribuidos, verificacao de programas concorrentes e paralelos, e raciocinio temporal. Estas aplicacoes requerem o desenvolvimento de provadores automaticos de teoremas para os sistemas modais utilizados nas suas formalizacoes. Este trabalho nas suas formalizacoes. Este trabalho apresenta a implementacao de um provador de teoremas para o sistema modal S4, denominado ProS4. Utilizam-se os tableaux semanticos de Fitting, sendo introduzidas novas heuristicas e estruturas de dados que fazemo provador ser eficiente, sem perder a decidibilidade. Na verificacao da validade ou nao de uma formula modal, o provador apresenta a demonstracao ou o modelo falsificador da formula em questao. O ProS4 pode ser extendido a Logica Temporal Linear de Programas, atraves da adicao do operador proximo (next) e linearizacao na geracao de novos mundos.

Este trabalho apresenta algoritmos de reconhecimento e parsing para um subconjunto da Gramática Livre de Contexto Lexicalizada (GLCL) da língua portuguesa. A GLCL apresentada neste trabalho estende o domínio de localidade de uma Gramática Livre de Contexto (GLC) do português fazendo com que um item lexical (símbolo terminal das gramáticas formais) apareça como parte das estruturas elementares sem alterar as estruturas das árvores utilizadas, o que é lingüisticamente muito significativo. A GLCL é uma forma restrita da Gramática de Adjunção de Árvores Lexicalizada (LTAG) que pode somente gerar linguagens livres de contexto, mantendo limites de complexidade de ordem cúbica, no pior caso, para o reconhecimento e parsing. Inicialmente, é apresentada uma introdução à área das Interfaces em Linguagem Natural para Banco de Dados (ILNBDs) referenciando as principais motivações e problemas encontrados no uso destas. O trabalho também apresenta uma introdução ao processamento da linguagem natural, situando gramáticas e analisadores sintáticos, buscando inserir este trabalho em seu contexto. Para um embasamento teórico é descrito o formalismo das GLCLs, com suas características, componentes, e operações de combinações entre os componentes. Os componentes principais do formalismo são dois conjuntos de árvores: árvores iniciais, as quais são combinadas por substituição, e árvores auxiliares, combinadas por uma forma restrita de adjunção.A seguir, é apresentado o subconjunto da língua escolhida. Algumas famílias de árvores foram descritas, mostrando um conjunto de orações na voz ativa, passiva, orações relativas, interrogativas e clivadas. A gramática está descrita de acordo com o formalismo da GLCL. Finalmente, algoritmos de reconhecimento e parsing para a GLCL da língua portuguesa serão desenvolvidos.