Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/17845
metadata.dc.type: Dissertação
metadata.dc.rights: Acesso Aberto
Title: Propriedades decidíveis de autômatos celulares finitos, híbridos, não-lineares, sensíveis e reversíveis
metadata.dc.creator: Alt, Leonardo de Sá
metadata.dc.contributor.advisor1: Oliveira, Gina Maira Barbosa de
metadata.dc.contributor.referee1: Amo, Sandra Aparecida de
metadata.dc.contributor.referee2: Oliveira, Pedro Paulo Balbi de
metadata.dc.description.resumo: Nós investigamos a decidibilidade e complexidade dos problemas do Predecessor e da Alcançabilidade em Autômatos Celulares Finitos, Híbridos, Reversíveis, Sensíveis e Não- Lineares. Demonstramos a reversibilidade do modelo, aqui definido como HSR, resolvendo assim o Problema do Predecessor. Utilizando a Forma Normal Disjuntiva para representar as funções de transição, conseguimos por derivadas parciais booleanas transformá-las para a Forma Normal Algébrica. Mostramos que utilizando a forma matricial e também as derivadas parciais booleanas é possível calcular vários passos da evolução temporal do modelo HSR em tempo polinomial; com isso demonstramos que o Problema da Alcançabilidade pertence à classe “Arthur-Merlin” AM2 e por isso não pode ser NP-Completo (a não ser que a hierarquia colapse). Também propusemos um novo método criptográfico baseado no modelo de AC HSR, cujas chaves criptográficas são combinações de funções de transição elementares, o que aumenta a eficiência do método sem abrir mão da segurança, já que mesmo tamanhos pequenos de reticulado fazem a cardinalidade do espaço de chaves ser muito grande.
Abstract: We investigated the decidability and complexity of the Predecessor and the Configuration Reachability problems in Non-Linear, Sensitive, Reversible, Hybridand Finite Cellular Automata. We demonstrated the model’s reversibility (defined here as HSR, Híbrido Sensível Reversível, or Hybrid Reversible Toggle), which, in turn solves the Predecessor’s Problem. Using Disjunctive Normal Form to represent transition functions, by Boolean partial derivatives, we could transform them to the Algebraic Normal Form. We show that using matrix form and Boolean partial derivatives sit is possible to calculate several HSR evolution steps in polynomial time; so we demonstrated that the Configuration Reachability Problem belongs to the complexity class “Arthur-Merlin” AM2 and cannot be NP-Complete (unless the hierarchy collapses). We also proposed a new cryptographic method based on the model HSR, whose cryptographic keys are combinations of elementary transition functions, what increases the method’s eficiency, without compromising security, since even small lattice sizes make the key space cardinality very large.
Keywords: Computação
Criptografia
Robôs
Autômatos celulares
Problema do predecessor
Problema da alcançabilidade
Pep
Crep
Criptografia
Reversibilidade
Sensitividade
Cellular automata
Predecessor problem
Configuration reachability problem
Cryptography
Reversibility
Sensitiviy
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal de Uberlândia
metadata.dc.publisher.program: Programa de Pós-graduação em Ciência da Computação
Citation: ALT, Leonardo de Sá. Propriedades decidíveis de autômatos celulares finitos, híbridos, não-lineares, sensíveis e reversíveis. 2013. 73 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2013.
URI: https://repositorio.ufu.br/handle/123456789/17845
Issue Date: 25-Feb-2013
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
PropriedadesDecidiveisAutomatos.pdfDissertação910.21 kBAdobe PDFView/Open


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