Propriedades decidíveis de autômatos celulares finitos, híbridos, não-lineares, sensíveis e reversíveis

• Ano de defesa: 2013
• Autor(a) principal: Alt, Leonardo de Sá
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Uberlândia; Brasil; Programa de Pós-graduação em Ciência da Computação
• Palavras-chave em Português: Computação; Criptografia; Robôs; Autômatos celulares; Problema do predecessor; Problema da alcançabilidade; Pep; Crep; Reversibilidade; Sensitividade; Cellular automata; Predecessor problem; Configuration reachability problem; Cryptography; Reversibility; Sensitiviy; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: https://repositorio.ufu.br/handle/123456789/17845

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.