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

dc.contributorOliveira, Gina Maira Barbosa de
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4784553Y0
dc.contributorAmo, Sandra Aparecida de
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4791545U6
dc.contributorOliveira, Pedro Paulo Balbi de
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4781786D0
dc.creatorAlt, Leonardo de Sá
dc.date2016-10-05T18:39:02Z
dc.date2016-10-05T18:39:02Z
dc.date2013-02-25
dc.date.accessioned2023-09-28T20:36:31Z
dc.date.available2023-09-28T20:36:31Z
dc.identifierALT, 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.
dc.identifierhttps://repositorio.ufu.br/handle/123456789/17845
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/9054726
dc.descriptionWe 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.
dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior
dc.descriptionDissertação (Mestrado)
dc.descriptionNó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.
dc.formatapplication/pdf
dc.languagepor
dc.publisherUniversidade Federal de Uberlândia
dc.publisherBrasil
dc.publisherPrograma de Pós-graduação em Ciência da Computação
dc.rightsAcesso Aberto
dc.subjectComputação
dc.subjectCriptografia
dc.subjectRobôs
dc.subjectAutômatos celulares
dc.subjectProblema do predecessor
dc.subjectProblema da alcançabilidade
dc.subjectPep
dc.subjectCrep
dc.subjectCriptografia
dc.subjectReversibilidade
dc.subjectSensitividade
dc.subjectCellular automata
dc.subjectPredecessor problem
dc.subjectConfiguration reachability problem
dc.subjectCryptography
dc.subjectReversibility
dc.subjectSensitiviy
dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
dc.titlePropriedades decidíveis de autômatos celulares finitos, híbridos, não-lineares, sensíveis e reversíveis
dc.typeDissertação


Este ítem pertenece a la siguiente institución