Explorando a noção de reversibilidade parcial de autômatos celulares elementares em reticulados cíclicos

AUTOR(ES)

Rodrigo da Silva Freitas

DATA DE PUBLICAÇÃO

2010

RESUMO

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.

ASSUNTO(S)

engenharia eletrica autômatos celulares regras reversíveis regras parcialmente reversíveis padrão de reversibilidade espaço elementar cellular automata reversible rules partially reversible rules reversibility pattern elementary space

Documentos Relacionados

• Automatizando a obtenção da complexidade baseada em linguagem regular de autômatos celulares elementares
• Reconhecimento de caracteres numéricos manuscritos com autômatos celulares, através da noção de protótipos espectrais
• Dinâmica de domínios e difusão em autômatos celulares determinísticos
• Representação ternária em algoritmos evolutivos para a obtenção de autômatos celulares binários
• Representação ternária em algoritmos evolutivos para a obtenção de autômatos celulares binários