Especificação e verificação de protocolos de votação em lógica linear com focusing

• Ano de defesa: 2018
• Autor(a) principal: Silva, Washington Cavalcante da
• Orientador(a): Vega, Carlos Alberto Olarte
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Programa de Pós-Graduação: PROGRAMA DE PÓS-GRADUAÇÃO EM MATEMÁTICA APLICADA E ESTATÍSTICA
• País: Brasil
• Palavras-chave em Português: Lógica linear; Focusing; Sistemas de transição; Protocolos de votação
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA APLICADA E ESTATÍSTICA
• Link de acesso: https://repositorio.ufrn.br/jspui/handle/123456789/25529

A lógica linear (LL) tem se consolidado como um bom arcabouço para especificar sistemas computacionais, uma vez que fórmulas podem ser interpretadas como recursos que podem ser consumidos e/ou produzidos. Além disso, do ponto de vista da Teoria da Prova, a LL reconcilia o aspecto construtivo da lógica intuicionista com a simetria da lógica clássica. Desta maneira, é possível, de uma forma mais flexível, modelar estados de um sistema como fórmulas lógicas, e as transições entre esses estados como etapas na construção de uma prova. No entanto, a busca por provas, em geral, não é determinística, pois existem diferentes maneiras de se provar a mesma proposição. Visando reduzir esse problema, um sistema de provas focado pode ser utilizado nesse processo de busca. A grosso modo, um sistema focado considera provas em forma normal, reduzindo assim as ocorrências de provas não essenciais que são sintaticamente diferentes, mas equivalentes no final do processo. Neste trabalho, é apresentada a prova da completude de um sistema focado para a LL, bem como outras propriedades essenciais desse sistema. Além disso, o sistema focado será utilizado para especificar e verificar protocolos de votação, que definem como deve ser escolhido um candidato, feita uma contagem de votos, e divulgado o resultado de uma eleição. Para que isso seja possível, dois protocolos de votação serão especificados formalmente utilizando sistemas de transição de estados, que modelam de forma natural os estados e comportamento de tais protocolos. Junto a isso, para cada sistema, uma especificação em LL será definida e demonstrada que é correta, ou seja, que um passo focado representa uma determinada transição no sistema de estados modelado. Por fim, propriedades inerentes aos protocolos de votação, como a garantia de que o resultado da eleição reflete o desejo dos eleitores, serão apresentadas e demonstradas através de derivações no sistema focado.