Restrições Complexas sobre Álgebras de Árvores e Aplicação a Gramáticas Lógicas
Nelma Moreira
Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823 4150-180 Porto, Portugal
Dezembro de 1997
Resumo
Nos últimos anos, a resolução de restrições simbólicas tem conhecido
um interesse crescente em várias áreas da Ciência de Computadores e,
em particular, na área da Linguística Computacional. Na verdade, as
restrições sobre álgebras de árvores racionais, podem contribuir
significativamente para a redução do espaço de procura em problemas de
Processamento de Linguagem Natural, ao mesmo tempo que aumentam a
expressividade dos formalismos. Nesta dissertação desenvolvemos um
modelo formal e computacional para linguagens de restrições sobre
árvores finitas, racionais e de estruturas de atributos. Embora as
teorias de primeira ordem destas álgebras sejam decidíveis, elas são
computacionalmente intratáveis. O nosso objectivo foi desenhar um
modelo teórico e algoritmos de decisão para lidar com este problema, e
que foram usados na implementação de vários formalismos gramaticais,
designados por
gramáticas lógicas com restrições (CLG).
As contribuições principais desta dissertação são:
- Resolutores completos de restrições complexas sobre álgebras de
árvores finitas e racionais. Para reduzir o custo computacional do
teste da satisfazilibidade de restrições complexas, a estratégia utilizada
baseia-se na factorização de informação determinística contida numa
restrição complexa que é utilizada para simplificar a restrição
resultante, retardando o mais possível a explosão das disjunções.
Desenvolvemos também sistemas de reescrita para a detecção de
factores comuns a elementos de disjunções e sistemas de reescrita
que utilizam informação negativas para a simplificação. Investigamos
o problema da eliminação de restrições negativas e apresentamos um
algoritmo de decisão para assinaturas finitas.
- Estabelecimento duma relação entre a álgebra de árvores
racionais e a álgebra de estruturas de atributos, de tal modo que o
problema da satisfazibilidade numa se reduz ao da outra.
- Um método de obtenção de modelos minimais para certas classes de
restrições satisfazíveis. Estas caracterizações são importantes
para a simplificação e detecção de restrições equivalentes.
- Uma implementação de baixo nível dos algoritmos principais dos
resolutores completos.
- Um calculus de ordem superior para descrições de árvores
baseado num lambda-calculus tipificado, que estende as técnicas desenvolvidas
para a resolução de restrições complexas. As descrições de ordem
superior foram utilizadas para as representações semânticas em
gramáticas de categorias para Linguagem Natural.
