Deciding difference logic in a Nelson-Oppen combination framework

AUTOR(ES)

Diego Caminha Barbosa de Oliveira

DATA DE PUBLICAÇÃO

2007

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

ASSUNTO(S)

formal methods difference logic nelson oppen sistemas de computacao smt - solvers decision procedure

Documentos Relacionados

• Remarks on an algebraic semantics for paraconsistent Nelson's logic
• Integrated care pathway for rectal cancer treatment: cross-sectional post-implementation study using a logic model framework
• Deciding Who Lives
• Parques verdes urbanos e transformação de comportamento: uma proposta de framework teórico entre a Transformative Service Research e a Service Dominant Logic
• On difficulties in deciding the aetiology of cataract.