Detalhes bibliográficos
| Ano de defesa: |
1999 |
| Autor(a) principal: |
Zanutto, Jefferson |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-022745/
|
Resumo: |
Dada uma teoria equacional T, isto é, um conjunto T de equações, uma pergunta que se faz é se os teoremas da teoria T podem, ou não, serem verificados através de um algoritmo que termina.Uma abordagem à esta questão, muito divulgada a partir da final da década de sessenta com o trabalho de Knut and Bendix, baseia-se na busca de sistemas de reescrita de termos completos para a teoria T dada, isto é, sistemas de reescrita completos que induzam as mesmas classes de congruência da teoria T. Muitos têm sido os esforços nas últimas décadas para o desenvolvimento de técnicas de completação de sistemas de reescrita com o intuito de conseguir-se obter sistemas completos para uma variedade cada vez maior de teorias equacionais. Neste trabalho, estudamos os aspectos básicos de teorias equacionais, incluindo seus sub-problemas como a unificação de termos e a terminação de sistemas de reescrita. Descrevemos dois algoritmos de completação de sistemas de reescrita, o algoritmo clássico de Knut and Bendix e o algoritmo de completação módulo teorial equacional, de Peterson and Stickel,generalizando o anterior. Por fim, apresentamos uma aplicação do uso de sistemas de reescrita para a Morfologia Matemática, uma área da computação com aplicações diretas no campo de processamento de imagens. Tanto a verificação da identidade entre operadores morfológicos quanto a simplificação de tais operadores são problemas de interesse no campo da morfologia matemática. Apresentamos, para a sub-classe dos operadores morfológicos invariantes por translação e isotônicos para imagens binárias, um método efetivo para a verificação de identidade entre tais operadores morfológicos, que se materializa na existência de um sistema de reescrita completo para a teoria dos reticulados distributivos. Discutimos, por fim, a aplicabilidade dessa abordagem para a simplificação de operadores morfológicos, tanto para o caso de implementações desses operadores em máquinas seqüenciais quanto em máquinas paralelas |
