Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/17845
Document type: Dissertação
Access type: Acesso Aberto
Title: Propriedades decidíveis de autômatos celulares finitos, híbridos, não-lineares, sensíveis e reversíveis
Author: Alt, Leonardo de Sá
First Advisor: Oliveira, Gina Maira Barbosa de
First member of the Committee: Amo, Sandra Aparecida de
Second member of the Committee: Oliveira, Pedro Paulo Balbi de
Summary: 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
Area (s) of CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Program: Programa de Pós-graduação em Ciência da Computação
Quote: 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
Date of defense: 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 PDFThumbnail
View/Open


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