1. Universidade Federal do Rio Grande do Norte
2. BDTD - Biblioteca Digital de Teses e Dissertações
3. Programa de Pós-Graduação em Sistemas e Computação
4. PPGSC - Mestrado em Sistemas e Computação

Title:	Deciding difference logic in a Nelson-Oppen combination framework
Authors:	Oliveira, Diego Caminha Barbosa de
Keywords:	Decision procedure;Difference logic;Formal methods;SMT - Solvers;Nelson oppen
Issue Date:	7-Nov-2007
Publisher:	Universidade Federal do Rio Grande do Norte
Citation:	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.
Portuguese Abstract:	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:	https://repositorio.ufrn.br/jspui/handle/123456789/17987
Appears in Collections:	PPGSC - Mestrado em Sistemas e Computação

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.