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 | Size | Format | |
---|---|---|---|---|
PropriedadesDecidiveisAutomatos.pdf | Dissertação | 910.21 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.