Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2017. / Submitted by Raquel Almeida (raquel.df13@gmail.com) on 2017-06-20T21:15:09Z No. of bitstreams: 1 2017_BrunodeAssisDelboni.pdf: 1000608 bytes, checksum: 0c7c86de2221eca903edd2ffda11ee2c (MD5) / Approved for entry into archive by Raquel Viana (raquelviana@bce.unb.br) on 2017-08-17T15:39:39Z (GMT) No. of bitstreams: 1 2017_BrunodeAssisDelboni.pdf: 1000608 bytes, checksum: 0c7c86de2221eca903edd2ffda11ee2c (MD5) / Made available in DSpace on 2017-08-17T15:39:39Z (GMT). No. of bitstreams: 1 2017_BrunodeAssisDelboni.pdf: 1000608 bytes, checksum: 0c7c86de2221eca903edd2ffda11ee2c (MD5) Previous issue date: 2017-08-17 / Esta dissertação tem como foco o estudo do problema de unificação módulo uma teoria equacional cuja assinatura contém um operador binário que satisfaz as identidades Associatividade, Comutatividade, Unidade e Nilpotência (ACUN), e que pode ou não conter um operador unário que satisfaz a identidade de homomorfismo (ACUNh), que é a teoria equacional do operador , amplamente utilizado em diversas ferramentas criptográficas, como MAUDE-NPA[10] que utiliza uma encriptação de grupos abelianos, incluindo ( ou exclusivo ), exponenciação e encriptação homomórfica. Primeiro apresentaremos alguns critérios para existência de soluções para problemas de ACUN(h)-unificação elementar com constantes que consiste em associar o problema de unificação à um sistema de equações lineares cujos coeficientes são elementos de ou , dependendo se o homomorfismo é ou não considerado. Segundo, apresentaremos um algoritmo para resolver problemas de ACUN(h)- unificação geral que retorna sempre um conjunto completo de unificadores. Finalmente, apresentaremos o estudo de um novo paradigma de unificação, a dizer, \emph{unificação assimétrica}, que consiste de obter unificadores de um problema de unificação com a propriedade de preservar formas normais do lado direito de cada equação de com relação a um sistema de reescrita convergente e coerente módulo uma teoria equacional . No caso particular da teoria equacional ACUN construiremos um algoritmo de conversão de ACUN-unificadores para ACUN-unificadores assimétricos. / This dissertation focuses on the study of unification problems modulo an equational theory whose signature contains a binary operator , which satisfies the identities of Associativity, Commutativity, Unity and Nilpotence (ACUN), and which may or not contain a unary operator satisfying the homomorphism identity (ACUNh), which is the equational theory for the operator XOR, Widely used on many cryptographic tools, like MAUDE[10], which uses group encryption, including XOR ( exclusive or ), exponentiation and homomorphic encryption. First we will present some criteria to the existence of solutions for elementary with constants ACUN(h)-unification problems which consist of associating a unification problem to a linear equation system whose coefficients are elements of or , depending one we are considering homomorphism or not. Second, we will present an algorithm to solve general ACUNh-unification problems which always returns a complete set of most general unifiers. Finally, we will present the study of a new unification paradigm, to say so, asymmetric unification, which consist of obtaining unifiers from the unification problem , with the property of preserving the normal form from of the right hand side of each equation in , considering a convergent and coherent rewriting system. In the particular case of the equational theory ACUN, we will also present an algorithm which takes as input ACUN-unifiers and outputs ACUN-asymmetric unifiers.