Made available in DSpace on 2016-03-15T19:37:32Z (GMT). No. of bitstreams: 1 Rodrigo da Silva Freitas.pdf: 462625 bytes, checksum: 0a15a8db6ef05a12c27f5668822ef98c (MD5) Previous issue date: 2010-08-12 / Fundo Mackenzie de Pesquisa / Cellular automata have been studied as computer models in many different forms. Several of its properties have been widely explored, among which reversibility stands out. This property is able to provide a cellular automaton the possibility of having their temporal evolution regenerated backward in time, regardless of its initial configuration, through an inverse cellular automaton. Reversibility is such a well characterized concept that many fundamental results associated with it have been obtained, such as the development of algorithms to enumerate all reversible one-dimensional cellular automata and the undecidability of this property for cellular automata in dimensions larger than 1. The driving force for the present research is to introduce a new concept involving the reversibility ability of a cellular automaton, the concept of partial reversibility, which is analysed herein according to the pre-images of all initial configurations of a rule, up to a certain length. This new concept may be useful for evolutionary searches for reversible cellular automata, to allow the use of cellular automata in tasks related somehow to the reversibility degree of a rule, or in applications where reversible rules are demonstrably employed, such as in cryptography. To that end, some parameters presumably related to reversibility are studied and compared, and empirical measures (lexicographical and numerical) are addressed. The results involving these empirical measures, showed that is possible to refer to a more partially reversible rule than another, besides revealing properties, apparently unknown so far, involving the pre-images of elementary rules. / Os autômatos celulares têm sido estudados como modelos computacionais de diversas formas. Diversas de suas propriedades têm sido amplamente exploradas, entre elas destacando-se a reversibilidade. Esta propriedade é capaz de fornecer a um autômato celular a possibilidade de ter sua evolução temporal refeita para trás no tempo, independentemente de sua configuração inicial, através de um autômato celular inverso. A reversibilidade é um conceito tão bem caracterizado que muitos resultados fundamentais associados a ela têm sido obtidos, tais como o desenvolvimento de algoritmos para enumerar todos os autômatos celulares unidimensionais reversíveis e a indecidibilidade desta propriedade para autômatos celulares com dimensão maior que 1. A ideia principal deste trabalho é introduzir um novo conceito envolvendo a capacidade de reversibilidade de um autômato celular, o conceito de reversibilidade parcial, que é analisado com base nas pré- imagens de todas configurações iniciais de uma regra, até um determinado tamanho de reticulado. Este novo conceito pode ser útil em buscas evolutivas de autômatos celulares reversíveis, a fim de permitir a utilização de autômatos celulares em tarefas associadas de alguma forma ao grau de reversibilidade de uma regra, ou ainda, em aplicações onde as regras reversíveis são comprovadamente empregadas, tal como em criptografia. Para tanto, alguns parâmetros supostamente relacionados à reversibilidade são estudados e comparados, e medidas empíricas (lexicográficas e numéricas) são abordadas. Os resultados obtidos envolvendo essas medidas empíricas mostraram que é possível referir-se a uma regra mais parcialmente reversível do que outra, além de revelar propriedades, até então desconhecidas, envolvendo as pré-imagens das regras elementares.

Made available in DSpace on 2016-03-15T19:38:03Z (GMT). No. of bitstreams: 1 RONALDO DE CASTRO CORREA.pdf: 1467426 bytes, checksum: a5e2b011297c7075c278d2dfd4502c98 (MD5) Previous issue date: 2015-11-23 / Cellular automata are discrete dynamic systems that by local action rules, even very simple, can present arbitrarily complex global processing. The reversibility is a property that a few rules have and guarantees the existence of an inverse rule capable of reversing the temporal evolution of the original rule. For a rule be reversible all possible configurations of lattices must have only one predecessor, i.e., only one pre-image. In this context, it had been proposed in the literature the concept of rules may be characterized by its relative partial reversibility, that is, rules can be more or less reversible than others. This notion is represented by the rule pre-image pattern, which is composed of the quantities ordered pre-images of all the possible configurations of lattices up to a maximum size. To sort the rules of the reversible for less reversible, or group them if they had the same reversibility was made lexicographical ordering patterns of pre-images. This paper reviewed the original definition, based on elementary cellular automata, although the results are applicable to any other one-dimensional family rules. Thus, proposed it was a measure of the reversibility level of a rule, also based on its default pre-image, but now from the probability of correctly reverse each possible configurations of lattices up to a given maximum size. This measure allows us to analyze the degree of reversibility of a rule in absolute terms and not relative to other rules. Thus, it becomes possible to individually analyze the reversibility levels of rules, making it possible to infer the degree of rules reversible for lattices arbitrarily larger than calculated, in particular, identifying rules that tend to be reversible when the size of the lattices tends to infinity. It was also possible to define an operation that, from their own state transitions rule, allows to obtain partially rules that have the same level of reversibility without the need of standard calculating preview image, which is extremely expensive computationally. / Autômatos celulares são sistemas dinâmicos discretos que, por meio de regras de ação local, até mesmo muito simples, podem apresentar processamento global arbitrariamente complexo. A reversibilidade é uma propriedade que poucas regras possuem e que garante a existência de uma regra inversa capaz de reverter a evolução temporal da regra original. Para uma regra ser reversível, todas as configurações possíveis de reticulado devem possuir somente uma única configuração antecessora, ou seja, uma única pré-imagem. Nesse contexto, havia sido proposto na literatura o conceito de regras poderem ser caracterizadas por sua reversibilidade parcial relativa, ou seja, regras poderem ser mais ou menos reversíveis que outras. Essa noção é representada por meio do padrão de pré-imagem da regra, que é composto pelas quantidades ordenadas de pré-imagens de todas as configurações possíveis de reticulado, até um tamanho máximo. Para classificar as regras das mais reversíveis para as menos reversíveis, ou agrupá-las caso possuíssem a mesma reversibilidade, era feita a ordenação lexicográfica dos padrões de pré-imagens. Este trabalho reavaliou a definição original, com base nos autômatos celulares elementares, apesar de os resultados serem aplicáveis a qualquer outra família unidimensional de regras. Assim, foi proposta uma grandeza que representa o nível de reversibilidade de uma regra, também baseada em seu padrão de pré-imagem, mas agora a partir da probabilidade de reverter corretamente cada configuração possível de reticulado, até um tamanho máximo dado. Tal medida permite analisar o nível de reversibilidade de uma regra em termos absolutos, e não mais relativamente a outras regras. Dessa forma, torna-se possível analisar individualmente os níveis de reversibilidade das regras, o que possibilitou inferir o nível de reversibilidade de regras para reticulados arbitrariamente maiores que os calculados, em particular, identificando regras que tendem a ser reversíveis conforme o tamanho do reticulado tende a infinito. Também foi possível definir uma operação que, a partir das próprias transições de estado de uma regra, permite obter parcialmente as regras que possuem o mesmo nível de reversibilidade, sem a necessidade do cálculo do padrão de pré-imagem, que é extremamente custoso computacionalmente.