Use este identificador para citar ou linkar para este item: https://repositorio.ufrn.br/jspui/handle/123456789/17987
Título: Deciding difference logic in a Nelson-Oppen combination framework
Autor(es): Oliveira, Diego Caminha Barbosa de
Palavras-chave: Decision procedure;Difference logic;Formal methods;SMT - Solvers;Nelson oppen
Data do documento: 7-Nov-2007
Editor: Universidade Federal do Rio Grande do Norte
Citação: OLIVEIRA, Diego Caminha Barbosa de. Deciding difference logic in a Nelson-Oppen combination framework. 2007. 71 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Rio Grande do Norte, Natal, 2007.
metadata.dc.description.resumo: O método de combinação de Nelson-Oppen permite que vários procedimentos de decisão, cada um projetado para uma teoria específica, possam ser combinados para inferir sobre teorias mais abrangentes, através do princípio de propagação de igualdades. Provadores de teorema baseados neste modelo são beneficiados por sua característica modular e podem evoluir mais facilmente, incrementalmente. Difference logic é uma subteoria da aritmética linear. Ela é formada por constraints do tipo x − y ≤ c, onde x e y são variáveis e c é uma constante. Difference logic é muito comum em vários problemas, como circuitos digitais, agendamento, sistemas temporais, etc. e se apresenta predominante em vários outros casos. Difference logic ainda se caracteriza por ser modelada usando teoria dos grafos. Isto permite que vários algoritmos eficientes e conhecidos da teoria de grafos possam ser utilizados. Um procedimento de decisão para difference logic é capaz de induzir sobre milhares de constraints. Um procedimento de decisão para a teoria de difference logic tem como objetivo principal informar se um conjunto de constraints de difference logic é satisfatível (as variáveis podem assumir valores que tornam o conjunto consistente) ou não. Além disso, para funcionar em um modelo de combinação baseado em Nelson-Oppen, o procedimento de decisão precisa ter outras funcionalidades, como geração de igualdade de variáveis, prova de inconsistência, premissas, etc. Este trabalho apresenta um procedimento de decisão para a teoria de difference logic dentro de uma arquitetura baseada no método de combinação de Nelson-Oppen. O trabalho foi realizado integrando-se ao provador haRVey, de onde foi possível observar o seu funcionamento. Detalhes de implementação e testes experimentais são relatados
URI: http://repositorio.ufrn.br:8080/jspui/handle/123456789/17987
Aparece nas coleções:PPGSC - Mestrado em Sistemas e Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
DiegoCBO.pdf551,58 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.